To reorient is easier than to orient: An on-line algorithm for reorientation of graphs

Abstract

We define an on-line (incremental) algorithm that, given a (possibly infinite) pseudo-transitive oriented graph, produces a transitive reorientation. This implies that a theorem of Ghouila-Houri is provable in ${RCA}_{0}$ and hence is computably true.

Keywords

On-line algorithm reverse mathematics comparability graphs pseudo-transitive graphs reorientations

Get full access to this article

View all access options for this article.

References

Bazhenov,

Downey,

Kalimullin and

Melnikov, Foundations of online structure theory, The Bulletin of Symbolic Logic 25(2) (2019), 141–181. doi:10.1017/bsl.2019.20.

Berge, Graphs and Hypergraphs, 2nd edn, North-Holland, Amsterdam, 1976.

Brattka,

Gherardi and

Pauly, Weihrauch complexity in computable analysis, in: Handbook of Computability and Complexity in Analysis,

Brattka and

Hertling, eds, Springer, New York, 2021, In press.

T.H.

Cormen,

C.E.

Leiserson,

R.L.

Rivest and

Stein, Introduction to Algorithms, 3rd edn, MIT Press, Massachusetts, 2009.

P.C.

Fishburn, Interval Orders and Interval Graphs, Wiley, New York, 1985.

Gallai , Transitiv orientierbare Graphen, Acta Mathematica. Academiae Scientiarum Hungaricae 18 (1967), 25–66, English translation in [13]. doi:10.1007/BF02020961.

Ghouila-Houri, Caractérisation des graphes non orientés dont on peut orienter les arětes de manière à obtenir le graphe d’une relation d’ordre, Les Comptes Rendus de l’Académie des Sciences 254 (1962), 1370–1371.

Ghouila-Houri, Flots et tensions dans un graphe, Ann. Sci. École Norm. Sup. (3) 81 (1964), 267–339. doi:10.24033/asens.1132.

P.C.

Gilmore and

A.J.

Hoffman, A characterization of comparability graphs and of interval graphs, Canadian Journal of Mathematics 16 (1964), 539–548. doi:10.4153/CJM-1964-055-5.

10.

M.C.

Golumbic, Algorithmic Graph Theory and Perfect Graphs, 2nd edn, Elsevier, 2004.

11.

Harzheim, Ordered Sets, Springer, New York, 2005.

12.

J.L.

Hirst, Combinatorics in subsystems of second order arithmetic, PhD thesis, The Pennsylvania State University, 1987.

13.

Maffray and

Preissmann, A translation of T. Gallai’s paper: “Transitiv orientierbare Graphen”, in: Perfect Graphs,

J.L.

Ramírez-Alfonsín and

B.A.

Reed, eds, Wiley, New York, 2001, pp. 25–66.

14.

S.G.

Simpson, Subsystems of Second Order Arithmetic, 2nd edn, Cambridge University Press, Cambridge, 2009.