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

1. Introduction

Let $(V, E)$ be an undirected graph, so that E is a set of unordered pairs of elements of V. We write $a E b$ to mean that ${a, b} \in E$ .

An asymmetric and irreflexive relation → is an orientation of $(V, E)$ if for every $a, b \in V$ we have $a E b$ if and only if $a \to b$ or $b \to a$ . An orientation → is transitive if for every $a, b, c \in V$ such that $a \to b$ and $b \to c$ we have also $a \to c$ . Graphs having a transitive orientation are also known as comparability graphs: in fact E is the comparability relation of the strict partial order →.

A characterization of comparability graphs was given by Alain Ghouila-Houri [7,8] (using a different terminology and dealing only with finite graphs) and reproved by Paul Gilmore and Alan Hoffman [9].1

¹
Further results were obtained by Gallai [6].

Theorem 1.1.

An undirected graph has a transitive orientation if and only if every cycle of odd length has a triangular chord.

Here a cycle is a sequence of vertices $a_{0}, \dots, a_{k}$ such that $a_{k} = a_{0}$ and $a_{i} E a_{i + 1}$ for every $i < k$ . (Notice that a vertex is allowed to occur more than once in a cycle.) The cycle has odd length if k is odd. The cycle has a triangular chord if either $a_{1} E a_{k - 1}$ or $a_{i} E a_{i + 2}$ for some $i < k - 1$ .

In Fig. 1 the left graph has a cycle of length nine with no triangular chord, while the right one has no cycles of odd length without triangular chords.

The forward direction of Theorem 1.1 is easily proved. The backward direction was proved directly by Gilmore and Hoffman, while the original proof by Ghouila-Houri uses an intermediate step. The latter approach is also taken in several expositions of the theorem ([2, Theorem 16.8], [5, Theorem 1.7], [11, Theorem 11.2.5]) and hinges on the following notion.

An orientation → is pseudo-transitive if for every $a, b, c \in V$ such that $a \to b$ and $b \to c$ we have also either $a \to c$ or $c \to a$ .

Ghouila-Houri proves the backward direction of Theorem 1.1 by first showing that if every cycle of odd length has a triangular chord then there exists a pseudo-transitive orientation, and then that any pseudo-transitive orientation can be further reoriented to obtain a transitive one.

Figure 1.

A graph which is not a comparability graph, to the left, and a comparability graph, to the right.

The effectiveness of Theorem 1.1 has already been studied, in particular using the framework of reverse mathematics ([14] is the basic reference in this area), by Jeff Hirst in his PhD thesis [12, Theorem 3.20]. Hirst indeed showed that a compactness argument (disguised as an application of Zorn’s lemma in [9] and of Rado’s theorem in [5,11]) is necessary for countable graphs and hence the theorem is not computably true. The following lemma includes Hirst’s theorem and provides a direct proof for it.

Lemma 1.2.

The following are equivalent over the base system ${RCA}_{0}$ :

${WKL}_{0}$ ;

every countable graph such that every cycle of odd length has a triangular chord has a transitive orientation;

every countable graph such that every cycle of odd length has a triangular chord has a pseudo-transitive orientation.

Proof.

(2) follows from (1) by a straightforward compactness argument, once the result is proved for finite graphs. The latter can be done in ${RCA}_{0}$ , following any of the proofs mentioned above.

The implication from (2) to (3) is trivial.

To check that (3) implies (1) we use [14, Lemma IV.4.4] stating that ${WKL}_{0}$ is equivalent to the statement that if $f, g : N \to N$ are injective functions such that $\forall m \forall n (f (m) \neq g (n))$ , then there exists X such that $\forall m (f (m) \in X \land g (m) \notin X)$ . Fix f and g as above, and define a graph $(V, E)$ as follows: $V = {a_{n}, b_{n}, c_{n}, d_{n} ∣ n \in N} \cup {x_{m}, y_{m} ∣ m \in N}$ and E is defined by the following clauses for each n and m: $\begin{matrix} \{\begin{matrix} c_{n} E a_{n} E b_{n} E c_{n} E d_{n}; \\ x_{m} E a_{n} & if f (m) = n; \\ y_{m} E b_{n} & if g (m) = n . \end{matrix} \end{matrix}$ Every cycle of odd length has a triangular chord because every connected component of $(V, E)$ is isomorphic to a subgraph of the right graph in Fig. 1. Let → be a pseudo-transitive orientation of E. It is easy to check that the set $\begin{matrix} X = {n \in N ∣ b_{n} \to a_{n} \leftarrow c_{n} \lor b_{n} \leftarrow a_{n} \to c_{n}} \end{matrix}$ contains the range of f and is disjoint from the range of g. □

The proof of Lemma 1.2 yields the following results in the framework of computability theory and of the Weihrauch lattice (see [3] for an introduction to this research program).

Lemma 1.3.

There exists a computable graph such that every cycle of odd length has a triangular chord which has no computable pseudo-transitive orientation.

Every computable graph such that every cycle of odd length has a triangular chord has a low transitive orientation.

Lemma 1.4.

Consider the multi-valued functions that map every countable graph such that every cycle of odd length has a triangular chord to the set of its transitive (resp. pseudo-transitive) orientations. Each of these two multi-valued functions is Weihrauch equivalent to choice on Cantor space.

Starting with [9] there has been an interest in algorithms providing transitive orientations for finite comparability graphs. For example, the influential textbook [10] devotes a whole chapter to algorithmic aspects of comparability graphs, including complexity issues. However, the first part of Lemma 1.3 shows that there is no algorithm to (pseudo-)transitively orient countable computability graphs. In particular, an algorithm which computes a (pseudo-)transitive orientation of finite comparability graphs cannot work in an incremental way (i.e. extending the previous orientation as new vertices are added to the graph), and thus is not on-line. Here we understand the notion of on-line algorithm as defined in [1], which is a recent survey of the theoretical study of on-line algorithms for computable structures.

Lemmas 1.2, 1.3, and 1.4 provide an analysis of the first step in Ghouila-Houri’s proof of Theorem 1.1. Our main interest is the analysis of the complexity of the second step of this proof, which is best stated using oriented graphs, i.e. directed graphs such that at most one of the edges between two vertices exist. In this paper we abbreviate ‘oriented graph’ as ograph. The notions of pseudo-transitivity and transitivity are readily extended to ographs, and a reorientation of an ograph is an ograph obtained by reversing some of the edges. Then the second step of Ghouila-Houri’s proof is the following result.

Theorem 1.5.

Every pseudo-transitive ograph has a transitive reorientation.

This is the main lemma in [7], the lemma on page 329 in [8], Theorem 16.7 in [2], Theorem 1.5 in [5], and Theorem 11.2.2 in [11]. Ghouila-Houri’s proof deals only with finite graphs and uses induction on the number of vertices. The same proof is presented in [2,5,11] and extended to the infinite case by some compactness argument. From this proof it is easy to extract an algorithm to transitively reorient finite pseudo-transitive ographs. However, the induction step requires, in a nutshell, partitioning the set of vertices into two subsets with specific properties, to reorient each of the induced subographs by induction hypothesis, and then to set the reorientation between them. Thus this algorithm is not incremental and does not apply to infinite ographs.

This analysis led us to conjecture that we could obtain results similar to Lemmas 1.2, 1.3 and 1.4 for Theorem 1.5. We were actually wrong and this is the main result of this paper. We state this result in various different ways (the first three items of the theorem correspond to the approaches of Lemmas 1.2, 1.3 and 1.4, respectively).

Main Theorem.

${RCA}_{0}$ proves that every countable pseudo-transitive ograph has a transitive reorientation;

every computable pseudo-transitive ograph has a computable transitive reorientation;

the multi-valued function that maps a countable pseudo-transitive ograph to the set of its transitive reorientations is computable;

there exists an on-line (incremental) algorithm to transitively reorient pseudo-transitive ographs;

Player II has a winning strategy for the following game: starting from the empty graph, at step $s + 1$ player I plays a pseudo-transitive extension $(V_{s} \cup {x_{s}}, \to_{s + 1})$ of the pseudo-transitive ograph $(V_{s}, \to_{s})$ he played at step s. Player II replies with a transitive reorientation $≺_{s + 1}$ of $\to_{s + 1}$ such that $≺_{s + 1}$ extends $≺_{s}$ she defined at step s. Player II wins if and only if she is always able to play.

We concentrate on proving (4) of the Main Theorem, as this easily implies (1), (2) and (3), while (5) is just a restatement in a different language of (4) for countable ographs.

We now make precise what we mean by an on-line (incremental) algorithm. We assume the input to consist of vertices coming one at a time together with all information about the edges connecting them to previous vertices. (So at step s the size of the input increases of at most s.) When the algorithm sees a new vertex, it must reorient all the edges connecting it to previous vertices while preserving the reorientations already set at previous stages.

We deal explicitly only with countable ographs; however it is easily seen that our algorithm applies to ographs of any cardinality, as long as the set of vertices can be well-ordered.

An upper bound for the complexity of the algorithm we define (when applied to finite pseudo-transitive ographs) is $O (| V |^{3})$ . The problem of orienting comparability graphs can be solved by an algorithm with complexity $O (δ \cdot | E |)$ , where δ is the maximum degree of a vertex ([10, Theorem 5.33]), and further fine-tuning has been subsequently made.

We now describe the organization of the paper. Section 2 contains the preliminary definitions and a presentation of two pseudo-transitive ographs with transitive reorientations which are the main obstacles in designing the algorithm. Sections 3 and 4 analyze in detail these two configurations. In Section 5 we present the on-line algorithm and prove its correctness. We also sketch the ideas needed to obtain the upper bound for the complexity mentioned above.

2. Preliminaries

In the introduction we have already introduced our terminology and we now give the formal definitions of the central notions.

Definition 2.1.
An ograph $(V, \to)$ is transitive if for each $a, b, c \in V$ , if $a \to b \to c$ , then $a \to c$ . $(V, \to)$ is pseudo-transitive if for each $a, b, c \in V$ , if $a \to b \to c$ , then $a \to c$ or $c \to a$ .

A relation R on V is a reorientation of →, if for each $a, b \in V$ , if $a \to b$ then either $a R b$ or $b R a$ and if $a R b$ then either $a \to b$ or $b \to a$ .

A transitive reorientation of $(V, \to)$ is a reorientation of $(V, \to)$ which is also transitive. In this case we often use ≺ in place of R.

A triple $(V, \to, ≺)$ is a Ghouila-Houri triple (GH-triple for short) if $(V, \to)$ is a pseudo-transitive ograph and ≺ a transitive reorientation of →.

Notice that each reorientation R of $(V, \to)$ preserves both →-comparability and →-incomparability. In other words, the undirected graphs associated with $(V, \to)$ and with $(V, R)$ coincide.
Notation 2.2.
Let $(V, \to)$ be an ograph and $a, b, c \in V$ .
$a - b$ means that either $a \to b$ or $b \to a$ ;

$N (a) = {b \in V ∣ a - b}$ is the neighborhood of a;

$a ∣ b$ means that neither $a \to b$ nor $b \to a$ ;

when we write ‘ $a - b$ by $pt (c)$ ’ we mean that we know that → is pseudo-transitive and we are deducing $a - b$ because we have either $a \to c \to b$ or $b \to c \to a$ .

Definition 2.3.
Let $(V, \to)$ be an ograph. If $V^{'} \supseteq V$ we say that $(V^{'}, \to^{'})$ is an extension of $(V, \to)$ if $(V^{'}, \to^{'})$ is an ograph such that for every $a, b \in V$ we have $a \to b$ if and only if $a \to^{'} b$ .

An on-line algorithm computing a transitive reorientation of a pseudo-transitive ograph must produce at each step a reorientation which can further be extended, in the sense made precise by the following definition.
Definition 2.4.
A GH-triple $(V, \to, ≺)$ is extendible if for every $(V \cup {x}, \to^{'})$ , pseudo-transitive extension of $(V, \to)$ , there exists $≺^{'}$ which extends ≺ and is such that $(V \cup {x}, \to^{'}, ≺^{'})$ is a GH-triple.

Some simple cases of GH-triples which are not extendible are depicted in Figs 2 and 3.
Example 2.5.
In Fig. 2 we have the transitive triangle examples: → is transitive on ${a, b, c}$ and the transitive reorientation is defined by $a ≺ c ≺ b$ . Notice that in the left ograph we have $a \to c \leftarrow b$ , while in the right one we have $a \leftarrow c \to b$ : in both cases all edges involving the vertex c have the same direction. We can add a vertex x connected to c by an edge going in the same direction and connected with neither a nor b. Then $({a, b, c, x}, \to^{'})$ is pseudo-transitive and if $≺^{'}$ is a reorientation of $\to^{'}$ extending ≺ we must have either $x ≺^{'} c$ or $c ≺^{'} x$ : both choices lead to the failure of transitivity of $≺^{'}$ .
Example 2.6.
In Fig. 3 we have the $2 \oplus 2$ example: there are two edges $a \to c$ and $b \to d$ (with no other edges between these four vertices) and the transitive reorientation defined by $a ≺ c$ and $d ≺ b$ . In the left ograph we add a vertex x such that $a \to^{'} x$ , $b \to^{'} x$ , $x ∣^{'} c$ and $x ∣^{'} d$ . Then $({a, b, c, d, x}, \to^{'})$ is pseudo-transitive. Suppose $≺^{'}$ were a transitive reorientation of $\to^{'}$ extending ≺: since $a -^{'} x$ and $x ∣^{'} c$ , then $a ≺ c$ implies $a ≺^{'} x$ ; since $b -^{'} x$ and $x ∣^{'} d$ , then $d ≺ b$ implies $x ≺^{'} b$ . But $a ≺^{'} x ≺^{'} b$ is not compatible with $a ∣ b$ . The situation in the right ograph is the same as the previous one as far as the first four vertices are concerned, but the new vertex x is now such that $x \to^{'} c$ , $x \to^{'} d$ , $x ∣^{'} a$ and $x ∣^{'} b$ . We can argue analogously to show that $({a, b, c, d, x}, \to^{'})$ is a pseudo-transitive ograph with no transitive reorientation extending ≺.

Figure 2.
The transitive triangle examples.

Figure 3.
The $2 \oplus 2$ example.

We eventually show that the examples above are the only obstructions to extendibility of a GH-triple. To do this we analyze in detail Examples 2.5 and 2.6 using the following notions.
Definition 2.7.
Let $(V, \to, ≺)$ be a GH-triple. If $(V \cup {x}, \to^{'})$ is a pseudo-transitive extension of $(V, \to)$ define $\begin{array}{l} N^{+} (x) = {a \in N (x) ∣ \forall b (a ≺ b \Rightarrow b \in N (x))}; \\ N^{-} (x) = {a \in N (x) ∣ \forall b (b ≺ a \Rightarrow b \in N (x))} . \end{array}$ (Here $N (x)$ is the neighborhood of x in $(V \cup {x}, \to^{'})$ .)
Remark 2.8.
Under the hypothesis of the previous definition we have that if $a \in N (x) ∖ N^{+} (x)$ , $b \in N^{+} (x)$ and $a - b$ , then $a ≺ b$ . In fact, since $a \notin N^{+} (x)$ there is $d ≻ a$ with $d ∣ x$ . If $b ≺ a$ , then $b ≺ d$ against $b \in N^{+} (x)$ . Thus $a ≺ b$ .

Similarly, if $c \in N (x) ∖ N^{-} (x)$ , $b \in N^{-} (x)$ , and $b - c$ , then $b ≺ c$ .

The next lemma states some properties of extendible GH-triples.

If $A, B \subseteq V$ we write $A ≺ B$ to mean that $a ≺ b$ for every $a \in A$ and $b \in B$ .
Lemma 2.9.
Let $(V, \to, ≺)$ be an extendible GH-triple. Then for any $(V \cup {x}, \to^{'})$ pseudo-transitive extension of $(V, \to)$ we have:
$N (x) = N^{+} (x) \cup N^{-} (x)$ ;

$N^{-} (x) ∖ N^{+} (x) ≺ N^{+} (x) ∖ N^{-} (x)$ .

Proof.
If condition (1) does not hold for some pseudo-transitive extension $(V \cup {x}, \to^{'})$ , then there exist $c \in N (x)$ and $a, b \notin N (x)$ such that $a ≺ c ≺ b$ . This impedes both $x ≺^{'} c$ and $c ≺^{'} x$ for any transitive reorientation of $\to^{'}$ with $≺^{'} \supseteq ≺$ . (Notice that we found in $(V, \to, ≺)$ a copy of one of the transitive triangle examples.)

If condition (2) does not hold for some pseudo-transitive extension $(V \cup {x}, \to^{'})$ , then there exist $a \in N^{-} (x) ∖ N^{+} (x)$ and $b \in N^{+} (x) ∖ N^{-} (x)$ such that $a ⊀ b$ . Since $a \in N^{-} (x) ∖ N^{+} (x)$ there exists c such that $a ≺ c$ and $c ∣^{'} x$ . Since $b \in N^{+} (x) ∖ N^{-} (x)$ , there exists d such that $d ≺ b$ and $d ∣^{'} x$ . If $≺^{'}$ were a transitive reorientation of $\to^{'}$ with $≺^{'} \supseteq ≺$ then these conditions imply respectively $a ≺^{'} x$ and $x ≺^{'} b$ ; it would follow $a ≺^{'} b$ , contrary to $a ⊀ b$ . (Notice that in this case we found in $(V, \to, ≺)$ a copy of the $2 \oplus 2$ example.) □
3. Avoiding the transitive triangle examples

This section is devoted to a careful study of the first condition of Lemma 2.9. The next lemma shows that this condition captures precisely the lack of the transitive triangle examples. Recall that in that situation $(V, \to, ≺)$ is a GH-triple. Moreover, there exist $a, b, c \in V$ such that $a ≺ c ≺ b$ and the new vertex x is connected with c, but not with a and b. Notice that this might happen only if a, b, c form a transitive triangle and either $a \to c \leftarrow b$ or $a \leftarrow c \to b$ .

Lemma 3.1.
Let $(V, \to, ≺)$ be a GH-triple and $(V \cup {x}, \to^{'})$ be a pseudo-transitive extension of $(V, \to)$ , then $N (x) = N^{+} (x) \cup N^{-} (x)$ is equivalent to $\forall a, b, c \in V (a ≺ c ≺ b \land x -^{'} c \Rightarrow x -^{'} a \lor x -^{'} b)$ .
Proof.
Notice that $c \in N (x) ∖ N^{+} (x) \cup N^{-} (x)$ means that there exist a and b such that $a ≺ c ≺ b$ and $a, b \notin N (x)$ . From this observation the equivalence is immediate. □

Lemma 3.1 involves all possible pseudo-transitive extensions of $(V, \to)$ by one vertex. It is convenient to have a characterization of the GH-triples such that $N (x) = N^{+} (x) \cup N^{-} (x)$ for every pseudo-transitive extension, which involves only the GH-triple itself. To this end we introduce two formulas, Φ and Ψ. In order to do this, we define formulas $φ (a, b, c)$ and $ψ (a, b, c)$ which do not mention the reorientation ≺. Notice that Lemmas 2.9 and 3.1 imply that the non extendibility of ≺ may be caused by only three vertices. With this in mind, it is not hard to understand the rationale for $φ (a, b, c)$ , $ψ (a, b, c)$ , Φ, and Ψ.
Definition 3.2.
Let $(V, \to, ≺)$ be a GH-triple. Let $φ (a, b, c)$ assert the existence of $e_{0}, \dots, e_{n} \in V$ such that:
$c \to e_{0}$ ;

$\forall i < n ((a \to e_{i} \land b \to e_{i} \to e_{i + 1}) \lor (e_{i + 1} \to e_{i} \to b \land e_{i} \to a))$ ;

$a \to e_{n} \to b \lor b \to e_{n} \to a$ .
Then Φ is $\begin{matrix} \forall a, b, c \in V (a \to c \leftarrow b \land a ≺ c ≺ b \Rightarrow φ (a, b, c)) . \end{matrix}$

Symmetrically, let $ψ (a, b, c)$ assert the existence of $e_{0}, \dots, e_{n} \in V$ such that:
$e_{0} \to c$ ;

$\forall i < n ((a \to e_{i} \land b \to e_{i} \to e_{i + 1}) \lor (e_{i + 1} \to e_{i} \to b \land e_{i} \to a))$ ;

$a \to e_{n} \to b \lor b \to e_{n} \to a$ .
Then Ψ is $\begin{matrix} \forall a, b, c \in V (a \leftarrow c \to b \land a ≺ c ≺ b \Rightarrow ψ (a, b, c)) . \end{matrix}$

Notice that the only difference between φ and ψ occurs in conditions ( $φ_{1}$ ) and ( $ψ_{1}$ ), where the direction of the edge is reversed. Φ and Ψ further differ in applying to triples such that $a \to c \leftarrow b$ and $a \leftarrow c \to b$ respectively.
Remark 3.3.
Let $(V, \to, ≺)$ be a GH-triple. Fix $a, b, c \in V$ . If $e_{0}, \dots, e_{n}$ witness $φ (a, b, c)$ (or $ψ (a, b, c)$ ) then they witness $φ (b, a, c)$ (resp. $ψ (b, a, c)$ ) as well.

The following duality principle is useful to avoid checking Φ and Ψ separately.
Remark 3.4.
Using Remark 3.3 it follows immediately that $(V, \to, ≺)$ satisfies Φ if and only if $(V, \leftarrow, ≻)$ (i.e. the ograph and the reorientation where all edges are reversed) satisfies Ψ.

We start with some properties concerning basic facts about φ and ψ.
Property 3.5.
Let $(V, \to)$ be a pseudo-transitive ograph. Suppose that $a \to c \leftarrow b$ and $φ (a, b, c)$ is witnessed by $e_{0}, \dots, e_{n}$ . Then there exists $k ⩽ n$ such that $e_{k}, \dots, e_{n}$ witness $φ (a, b, d)$ for each $d \in V$ such that $d ∣ c$ and $a - d - b$ .

The same holds starting from $a \leftarrow c \to b$ and $ψ (a, b, c)$ , and concluding that $e_{k}, \dots, e_{n}$ witness $ψ (a, b, d)$ .
Proof.
Suppose we are in the first case, i.e. $a \to c \leftarrow b$ and $e_{0}, \dots, e_{n}$ witness $φ (a, b, c)$ . Let $k ⩽ n$ be largest such that $c \to e_{k}$ , and notice that $e_{k}, \dots, e_{n}$ witness $φ (a, b, c)$ as well.

We claim that $e_{i} \to c$ for all i such that $k < i ⩽ n$ . The claim is proved by a ‘backward’ induction. We obtain $e_{n} - c$ by ( $φ_{3}$ ) and $pt (b)$ or $pt (a)$ . Hence $e_{n} \to c$ by our assumption (unless $n = k$ ). Suppose now that $e_{i + 1} \to c$ . If $e_{i} \to a$ , then $e_{i} - c$ by $pt (a)$ . Otherwise, $e_{i} \to e_{i + 1}$ by ( $φ_{2}$ ) and so $e_{i} - c$ by $pt (e_{i + 1})$ . Hence, if $i > k$ we have $e_{i} \to c$ .

Let now d be such that $d ∣ c$ and $a - d - b$ . In particular we have $a \to d \leftarrow b$ . Notice that to check that $e_{k}, \dots, e_{n}$ witness $φ (a, b, d)$ conditions ( $φ_{2}$ ) and ( $φ_{3}$ ) are identical to conditions ( $φ_{2}$ ) and ( $φ_{3}$ ) of $φ (a, b, c)$ , since they concern only the vertices a and b. We are left to prove that condition ( $φ_{1}$ ) is satisfied, namely that $d \to e_{k}$ . Since $d ∣ c$ and $c \to e_{k}$ it suffices to show that $d - e_{k}$ .

To this end we prove that indeed we have $e_{i} - d$ for all i such that $k ⩽ i ⩽ n$ , again by a ‘backward’ induction. Since $a \to d \leftarrow b$ and either $e_{n} \to a$ or $e_{n} \to b$ by ( $φ_{3}$ ), we have $e_{n} - d$ by either $pt (a)$ or $pt (b)$ . Now, assuming $i ⩾ k$ and $e_{i + 1} - d$ so that $d - e_{i + 1} - c$ , we must have $e_{i + 1} \to d$ because $e_{i + 1} \to c$ by the choice of k. If $a \to e_{i}$ condition ( $φ_{2}$ ) of $φ (a, b, c)$ implies $e_{i} \to e_{i + 1}$ and hence $e_{i} - d$ by $pt (e_{i + 1})$ . If $e_{i} \to a$ , then $e_{i} - d$ by $pt (a)$ , since $a \to d$ .

If $a \leftarrow c \to b$ and $e_{0}, \dots, e_{n}$ witness $ψ (a, b, c)$ the argument is similar with obvious changes. □
Property 3.6.
Let $(V, \to)$ be a pseudo-transitive ograph and let $v, u, e_{0}, \dots, e_{n} \in V$ . Suppose $u ∣ v$ , $u - e_{0}$ and $\forall i < n (v \to e_{i} \to e_{i + 1} \lor e_{i + 1} \to e_{i} \to v)$ . Then $u - e_{i}$ for each $i ⩽ n$ .
Proof.
The proof is by induction on i. The base case holds by assumption, so assume $u - e_{i}$ for $i < n$ . If $u \to e_{i}$ , then $v \to e_{i}$ because $u ∣ v$ . Thus $e_{i} \to e_{i + 1}$ and $u - e_{i + 1}$ by $pt (e_{i})$ . If $e_{i} \to u$ the argument is symmetric inverting the arrows. □

We can now show that Φ and Ψ are sufficient for the first condition of Lemma 2.9.
Lemma 3.7.
Let $(V, \to, ≺)$ be a GH-triple. If Φ and Ψ are satisfied, then for each $(V \cup {x}, \to^{'})$ pseudo-transitive extension of $(V, \to)$ we have $N (x) = N^{+} (x) \cup N^{-} (x)$ .
Proof.
Fix $(V \cup {x}, \to^{'})$ . By Lemma 3.1 it suffices to show that for any $a, b, c \in V$ such that $a ≺ c ≺ b$ and $x -^{'} c$ either $x -^{'} a$ or $x -^{'} b$ .

If $b \to c \to a$ then $x \to^{'} c$ implies $x -^{'} a$ , while $c \to^{'} x$ implies $x -^{'} b$ . If $a \to c \to b$ the situation is similar.

If $a \to c \leftarrow b$ then Φ implies that $ϕ (a, b, c)$ holds. Let $e_{0}, \dots, e_{n}$ witness $φ (a, b, c)$ . Assume $x -^{'} c$ . If $c \to^{'} x$ , then both $a -^{'} x$ and $b -^{'} x$ follow immediately by $pt (c)$ . Otherwise we have $x \to^{'} c$ , and suppose towards a contradiction that $x ∣^{'} a$ and $x ∣^{'} b$ . Notice that $x \to^{'} c \to e_{0}$ implies $x -^{'} e_{0}$ . Hence by condition ( $φ_{2}$ ) and Property 3.6 it holds that $\forall i ⩽ n (x -^{'} e_{i})$ . In particular we have $x -^{'} e_{n}$ , and then one of $x -^{'} a$ and $x -^{'} b$ by $pt (e_{n})$ follows by ( $φ_{3}$ ).

If $a \leftarrow c \to b$ we argue similarly, using Ψ. □

We now prove that Φ and Ψ are necessary conditions for $N (x) = N^{+} (x) \cup N^{-} (x)$ .
Lemma 3.8.
Let $(V, \to, ≺)$ be a GH-triple such that one of Φ and Ψ fails. Then there is a pseudo-transitive extension $(V \cup {x}, \to^{'})$ of $(V, \to)$ such that $N (x) \neq N^{+} (x) \cup N^{-} (x)$ and hence $(V, \to, ≺)$ is not extendible by Lemma 2.9 .
Proof.
We assume the failure of Φ: if Ψ fails the argument is symmetric.

Let $a, b, c \in V$ be such that $a \to c \leftarrow b$ , $a ≺ c ≺ b$ and $\neg φ (a, b, c)$ . We fix $x \notin V$ and define an extension $\to^{'}$ of $(V, \to)$ to $V \cup {x}$ in stages, as an increasing union $\to^{'} = ⋃_{n \in N} \to_{n}$ . For each stage n, $\to_{n}$ is defined as follows:
$\to_{0}$ extends → by adding the single edge $x \to_{0} c$ ;

$\to_{n + 1}$ extends $\to_{n}$ by adding edges $\begin{matrix} \{\begin{matrix} x \to_{n + 1} u & if \exists v ((x \to_{n} v \to u) \lor (u \to v \to_{n} x)) and a \to u \leftarrow b; \\ u \to_{n + 1} x & if \exists v ((x \to_{n} v \to u) \lor (u \to v \to_{n} x)) and a \leftarrow u \to b . \end{matrix} \end{matrix}$
Notice that $x -^{'} c$ but $x ∣^{'} a$ and $x ∣^{'} b$ and hence $c \in N (x)$ but $c \notin N^{+} (x) \cup N^{-} (x)$ . Therefore to complete the proof it suffices to check the pseudo-transitivity of $\to^{'}$ . We first make a couple of preliminary observations. Claim 3.8.1.
For all $u \in V$ such that there exists $v \in V$ satisfying either $x \to^{'} v \to u$ or $u \to v \to^{'} x$ we have $a - u - b$ .
Proof.
Let us first suppose that $x \to^{'} v \to u$ holds. By definition of $\to^{'}$ (or by hypothesis when $v = c$ ) it holds that $a \to v \leftarrow b$ . Hence $a - u - b$ by $pt (v)$ . If $u \to v \to^{'} x$ the argument is similar. □
Claim 3.8.2.
If $u \in V$ is such that $u \neq c$ and $u -_{1} x$ then $c \to u$ .
Proof.
Let us suppose that $u \neq c$ and $u -_{1} x$ , so that $u -_{0} x$ does not hold. The definition of $\to_{1}$ implies that for some v we have either $x \to_{0} v \to u$ or $u \to v \to_{0} x$ . Since the only v such that $v -_{0} x$ is c and $x \to_{0} c$ we must have the first possibility with $v = c$ , so that $c \to u$ holds. □

In order to show that $\to^{'}$ is pseudo-transitive, we have to consider the following three cases for $v, u \in V$ :
$v \to^{'} x \to^{'} u$ . Then $v - u$ because $v \to a \to u$ by definition of $\to^{'}$ ;

$x \to^{'} v \to u$ . Then Claim 3.8.1 guarantees that $a - u - b$ . Let n be the least stage such that $x \to_{n} v$ . If $a \to u \leftarrow b$ or $a \leftarrow u \to b$ , then $x -_{n + 1} u$ by definition of $\to_{n + 1}$ . Thus we assume that either $a \to u \to b$ or $b \to u \to a$ . Since n is the minimum stage such that $x \to_{n} v$ , there exists $e_{n - 2}$ such that $x -_{n - 1} e_{n - 2} - v$ and $x \to_{n - 1} e_{n - 2} \Leftrightarrow e_{n - 2} \to v$ . Notice that $x -_{n - 2} e_{n - 2}$ does not hold, otherwise we would have $x \to_{n - 1} v$ . Analogously, there must be an $e_{n - 3}$ such that $x -_{n - 2} e_{n - 3} - e_{n - 2}$ and $x \to_{n - 2} e_{n - 3} \Leftrightarrow e_{n - 3} \to e_{n - 2}$ . For each step $i < n$ , we can repeat this search of $e_{i - 2}$ witnessing that $x -_{i} e_{i - 1}$ . After $n - 1$ steps we get to $x -_{1} e_{0}$ and, since $x -_{0} e_{0}$ does not hold, $e_{0} \neq c$ . This means, by Claim 3.8.2, that $c \to e_{0}$ . Let j be maximum such that $c \to e_{j}$ and set $e_{n - 1} = v$ and $e_{n} = u$ . We claim that $e_{j}, \dots, e_{n}$ witness $φ (a, b, c)$ . To this end we need to check the three clauses in the definition of $φ (a, b, c)$ :

$c \to e_{j}$ by hypothesis.

Fix $i < n$ : $e_{i} - e_{i + 1}$ holds by our choice of the sequence of the $e_{i}$ ’s and we have either $a \to e_{i} \leftarrow b$ or $a \leftarrow e_{i} \to b$ by definition of $\to_{i}$ . Moreover, if $x \to_{i + 1} e_{i}$ , then $b \to e_{i}$ , by definition of $\to_{i + 1}$ , and $e_{i} \to e_{i + 1}$ , by choice of $e_{i}$ . If $e_{i} \to_{i + 1} x$ the argument is similar.

$a \to e_{n} \to b$ or $b \to e_{n} \to a$ by hypothesis.

$u \to v \to^{'} x$ . This is similar to the previous case.
□

Summarizing the results obtained in Lemma 3.7 and Lemma 3.8 we obtain: Corollary 3.9.
Let $(V, \to, ≺)$ be a GH-triple. The following are equivalent:
for each pseudo-transitive extension $(V \cup {x}, \to^{'})$ of $(V, \to)$ , it holds that $N (x) = N^{+} (x) \cup N^{-} (x)$ ;

Φ and Ψ are satisfied.

4. Avoiding the $2 \oplus 2$ example

This section is devoted to study more carefully the second condition of Lemma 2.9. The next lemma shows that, assuming that $N (x) = N^{+} (x) \cup N^{-} (x)$ , this condition captures precisely the lack of the $2 \oplus 2$ example. Recall that in that example $(V, \to, ≺)$ is a GH-triple and there exist $a, b, c, d \in V$ such that $a ≺ c$ , $d ≺ b$ , $a ∣ b$ , $a ∣ d$ , $c ∣ b$ , and $c ∣ d$ . Then, a new vertex x is connected with a and b but not with c and d, or vice versa. Notice that this is possible only if either $a \to c$ and $b \to d$ , or $c \to a$ and $d \to b$ .

Lemma 4.1.
Let $(V, \to, ≺)$ be a GH-triple and $(V \cup {x}, \to^{'})$ a pseudo-transitive extension of $(V, \to)$ . We use Λ to denote the following property of $(V \cup {x}, \to^{'})$ and ≺: $\begin{matrix} \forall a, b, c, d \in V (a ∣ b \land c ∣ d \land a ≺ c \land d ≺ b \land x -^{'} a \land x -^{'} b \Rightarrow x -^{'} d \lor x -^{'} c) \end{matrix}$ Then:
if Λ holds then $N^{-} (x) ∖ N^{+} (x) ≺ N^{+} (x) ∖ N^{-} (x)$ ;

if $N (x) = N^{+} (x) \cup N^{-} (x)$ and $N^{-} (x) ∖ N^{+} (x) ≺ N^{+} (x) ∖ N^{-} (x)$ then Λ holds.

Proof.
$(1)$ Assume $N^{-} (x) ∖ N^{+} (x) ⊀ N^{+} (x) ∖ N^{-} (x)$ , i.e. there exist $a \in N^{-} (x) ∖ N^{+} (x)$ and $b \in N^{+} (x) ∖ N^{-} (x)$ such that $a ⊀ b$ . Since $a \notin N^{+} (x)$ there is $c ≻ a$ with $c ∣ x$ . Since $b \notin N^{-} (x)$ there is $d ≺ b$ with $d ∣ x$ . If $b ≺ a$ , then $b ≺ c$ but this is impossible since $c ∣ x$ and $b \in N^{+} (x)$ . Since we are assuming $a ⊀ b$ we have $a ∣ b$ .

We claim that $c ∣ d$ also holds. Since $a - x - b$ , but $a ∣ b$ , then either $a \to x \leftarrow b$ or $a \leftarrow x \to b$ . The argument for the two cases is similar, so let us assume that $a \to x \leftarrow b$ . This implies $a \to c$ and $b \to d$ because $c ∣ x$ and $x ∣ d$ . Hence if $c \to d$ , then $a - d$ by $pt (c)$ . Since $a ∣ b$ and $d ≺ b$ , it must be $d ≺ a$ but this contradicts $a \in N^{-} (x)$ . If $d \to c$ , then $c - b$ by $pt (d)$ . Since $a ∣ b$ and $a ≺ c$ , it must be $b ≺ c$ which contradicts $b \in N^{+} (x)$ . We have thus shown that $c ∣ d$ as claimed.

Now a, b, c and d witness the failure of Λ.

$(2)$ Assume that $a, b, c, d \in V$ witness the failure of Λ. Then $a \notin N^{+} (x)$ , $b \notin N^{-} (x)$ and $a ⊀ b$ . If $N (x) = N^{+} (x) \cup N^{-} (x)$ holds then $a \in N^{-} (x)$ and $b \in N^{+} (x)$ , showing that $N^{-} (x) ∖ N^{+} (x) ≺ N^{+} (x) ∖ N^{-} (x)$ fails. □
Observation 4.2.
Notice that the first four conjuncts of the antecedent of the implication appearing in Λ imply that a, b, c and d form a $2 \oplus 2$ because $c ∣ b$ and $a ∣ d$ follow from these. In fact, if $c - b$ , then $a ≺ c$ and $a ∣ b$ imply that $b ≺ c$ , but then $d - c$ contrary to the assumption. A similar argument shows that $a ∣ d$ .

We now define two formulas Θ and Σ characterizing the reorientations such that the condition Λ of Lemma 4.1 is satisfied whenever $N (x) = N^{+} (x) \cup N^{-} (x)$ . As for Φ and Ψ, the main feature of Θ and Σ is that they mention only $(V, \to)$ and ≺. In order to define Θ and Σ it is necessary to define $θ (a, b, c, d)$ and $σ (a, b, c, d)$ (which do not mention ≺).
Definition 4.3.
Let $(V, \to, ≺)$ be a GH-triple. Let $θ (a, b, c, d)$ assert the existence of $e_{0}, \dots, e_{n} \in V$ such that:
$e_{0} \to b$ ;

$\forall i < n (e_{i + 1} \to e_{i} \to d)$ ;

$d \to e_{n}$ ;

$e_{n} ∣ a$ .
Then Θ is $\begin{matrix} \forall a, b, c, d \in V (a \to c \land b \to d \land a ∣ b \land c ∣ d \land a ≺ c \land d ≺ b \Rightarrow θ (a, b, c, d) \lor θ (b, a, d, c)) . \end{matrix}$ Symmetrically, let $σ (a, b, c, d)$ assert the existence of $e_{0}, \dots, e_{n} \in V$ such that:
$d \to e_{0}$ ;

$\forall i < n (b \to e_{i} \to e_{i + 1})$ ;

$e_{n} \to b$ ;

$e_{n} ∣ c$ .
Then Σ is $\begin{matrix} \forall a, b, c, d \in V (a \to c \land b \to d \land a ∣ b \land c ∣ d \land a ≺ c \land d ≺ b \Rightarrow σ (a, b, c, d) \lor σ (b, a, d, c)) . \end{matrix}$
Example 4.4.
Suppose $({a, b, c, d, e}, \to)$ is the pseudo-transitive graph whose only edges are $a \to c$ , $b \to d$ and $d \to e \to b$ . Then $θ (a, b, c, d)$ and $σ (a, b, c, d)$ hold with $n = 0$ and $e_{0} = e$ . Thus a $2 \oplus 2$ such as the one obtained restricting → to ${a, b, c, d}$ can satisfy θ and σ simply because one of its edges belongs to a non transitive triangle. See the first paragraph of the proof of lemma 5.12 below for more on this.
Remark 4.5.
Let $(V, \to, ≺)$ be a GH-triple. Suppose $e_{0}, \dots, e_{n}$ witness $θ (a, b, c, d)$ for some $a, b, c, d \in V$ . Clearly, if there is an $i > 0$ such that $e_{i} \to b$ , then $e_{i}, \dots, e_{n}$ witness $θ (a, b, c, d)$ as well. Thus we can assume that for every $i ⩽ n$ with $i > 0$ we have $b \to e_{i}$ whenever $b - e_{i}$ . Under this assumption it actually holds that $b \to e_{i}$ holds for every $i ⩽ n$ with $i > 0$ . In fact, $b - e_{n}$ by $pt (d)$ and if $b \to e_{i + 1}$ , then $b - e_{i}$ by $pt (e_{i + 1})$ .

Before proving the usefulness of Θ and Σ, we would like to comment on their mutual relationship and on the difference between the connection between Θ and Σ and the connection between Φ and Ψ. Let $(V, \to, ≺)$ be a GH-triple and suppose $a, b, c, d \in V$ satisfy the antecedent of Θ and Σ (which is the same). Consider a pseudo-transitive extension $(V \cup {x, y}, \to^{'})$ such that $a \to^{'} x \leftarrow^{'} b$ and $c \leftarrow^{'} y \to^{'} d$ . The two extensions correspond respectively to the left and right ograph of Fig. 2. As explained at the beginning of this section, if either x is incomparable with both c and d or if y is incomparable with both a and b, then $(V, \to, ≺)$ is not extendible. We emphasize that under these hypotheses we could have both x and y witnessing the non extendibility of $(V, \to, ≺)$ . To compare this situation with the one Φ and Ψ take care of, suppose $a \to b \to c \leftarrow a$ and add x and y such that $a \to x$ and $y \to c$ . Since $c ≺ a ≺ b$ and $a ≺ c ≺ b$ cannot occur simultaneously, only one of x and y can witness (if $φ (a, b, c)$ , resp. $ψ (b, c, a)$ , fails) the non extendibility of $(V, \to, ≺)$ .

Despite the previous considerations the next lemma shows that x witnesses the non extendibility of $(V, \to, ≺)$ if and only if y does.
Lemma 4.6.
Let $(V, \to)$ be a pseudo-transitive ograph and suppose $a, b, c, d \in V$ are such that $a \to c$ , $b \to d$ , $a ∣ b$ and $d ∣ c$ . Then $θ (a, b, c, d)$ holds if and only if $σ (a, b, c, d)$ does.

Therefore, if $(V, \to, ≺)$ is a GH-triple then Θ holds if and only if Σ does.
Proof.
Since the antecedents of Σ and Θ coincide and imply the hypothesis of the first statement, it is clear that the second statement follows from the first.

For the forward direction of the first statement, let $e_{0}, \dots, e_{n}$ witness $θ (a, b, c, d)$ . By Remark 4.5 we can assume that $b \to e_{i}$ whenever $i > 0$ . We claim that $e_{n}, \dots, e_{0}$ witness $σ (a, b, c, d)$ . In fact, conditions ( $σ_{1}$ ) and ( $σ_{3}$ ) of $σ (a, b, c, d)$ are exactly conditions ( $θ_{3}$ ) and ( $θ_{1}$ ) of $θ (a, b, c, d)$ . Condition ( $σ_{2}$ ) of $σ (a, b, c, d)$ is now $\forall i < n (b \to e_{i + 1} \to e_{i})$ and follows easily from our assumption on the $e_{i}$ ’s and from condition ( $θ_{2}$ ) of $θ (a, b, c, d)$ . We are left with showing condition ( $σ_{4}$ ) of $σ (a, b, c, d)$ , i.e. $e_{0} ∣ c$ . Suppose on the contrary that $e_{0} - c$ . Since $c ∣ d$ , by Property 3.6 it follows that $\forall i ⩽ n (c - e_{i})$ . In particular, $c - e_{n}$ and so $e_{n} \to c$ because $a ∣ e_{n}$ by ( $θ_{4}$ ) of $θ (a, b, c, d)$ . But then $c - d$ by $pt (e_{n})$ , contrary to the assumptions.

The proof of the backward direction is analogous. □

Thanks to the previous lemma it suffices to concentrate on Θ.

The following duality principle is analogous to Remark 3.4. It is not needed elsewhere and we include it here for completeness without proof.
Remark 4.7.
Notice that the GH-triple $(V, \to, ≺)$ satisfies Θ if and only if the GH-triple $(V, \leftarrow, ≻)$ satisfies Θ.
Lemma 4.8.
Let $(V, \to, ≺)$ be a GH-triple. Let $a, b, c, d \in V$ be such that $a \to c$ , $b \to d$ , $a ∣ b$ , and $d ∣ c$ and assume that $θ (a, b, c, d)$ holds. Then for each $(V \cup {x}, \to^{'})$ pseudo-transitive extension of $(V, \to)$ if $a -^{'} x -^{'} b$ holds we have $x -^{'} d$ , and if $c -^{'} x -^{'} d$ holds we have $x -^{'} b$ .
Proof.
Let $(V \cup {x}, \to^{'})$ be a pseudo-transitive extension of $(V, \to)$ with $a -^{'} x -^{'} b$ . Notice that, since $a ∣ b$ , either $a \leftarrow^{'} x \to^{'} b$ or $a \to^{'} x \leftarrow^{'} b$ . In the first case $pt (a)$ and $pt (b)$ guarantee that $c -^{'} x -^{'} d$ , so we concentrate on the other case.

Suppose that $a \to^{'} x \leftarrow^{'} b$ and let $e_{0}, \dots, e_{n}$ witness $θ (a, b, c, d)$ . Towards a contradiction, assume $x ∣^{'} d$ . Notice that $x -^{'} e_{0}$ by $pt (b)$ (we use condition ( $θ_{1}$ )). Hence by condition ( $θ_{2}$ ) and Property 3.6 it holds that $\forall i ⩽ n (x -^{'} e_{i})$ , so that in particular $x -^{'} e_{n}$ . It cannot hold that $x \to e_{n}$ , otherwise $a - e_{n}$ by $pt (x)$ contrary to ( $θ_{4}$ ). Hence $e_{n} \to x$ holds. Moreover, $d \to e_{n}$ by condition ( $θ_{3}$ ) and so $pt (e_{n})$ implies $d -^{'} x$ .

A similar argument shows that $c -^{'} x -^{'} d$ implies $x -^{'} b$ . The only change is due to the fact that when $c \leftarrow^{'} x \to^{'} d$ then we use $σ (a, b, c, d)$ , which holds by Lemma 4.6. □

We can now show that Θ is sufficient for the second condition of Lemma 2.9.
Lemma 4.9.
Let $(V, \to, ≺)$ be a GH-triple satisfying Θ. For each $(V \cup {x}, \to^{'})$ pseudo-transitive extension of $(V, \to)$ we have $N^{-} (x) ∖ N^{+} (x) ≺ N^{+} (x) ∖ N^{-} (x)$ .
Proof.
By Lemma 4.1.1 it suffices to prove condition Λ. Fix $a, b, c, d \in V$ such that $a ≺ c$ , $d ≺ b$ , $a ∣ b$ , and $c ∣ d$ and assume that $a -^{'} x -^{'} b$ . We need to prove that either $x -^{'} c$ or $x -^{'} d$ .

Since $a - c$ and $d - b$ there are four possible situations. If $a \to c$ and $d \to b$ , but $x ∣^{'} c$ , then $a \to^{'} x \leftarrow^{'} b$ and $x -^{'} d$ follows by $pt (b)$ . If $c \to a$ and $b \to d$ the argument is similar. If instead $a \to c$ and $b \to d$ notice that Θ implies $θ (a, b, c, d)$ or $θ (b, a, d, c)$ : then Lemma 4.8 yields the conclusion. The last possibility is $c \to a$ and $d \to b$ , where we use the second part of Lemma 4.8 (in this case a, b, c, d play roles which are opposite to those of the Lemma). □

We now prove that Θ is necessary for $N^{-} (x) ∖ N^{+} (x) ≺ N^{+} (x) ∖ N^{-} (x)$ if Φ and Ψ hold.
Lemma 4.10.
Let $(V, \to, ≺)$ be a GH-triple such that Φ and Ψ hold and Θ fails. Then there is a pseudo-transitive extension $(V \cup {x}, \to^{'})$ of $(V, \to)$ such that $N^{-} (x) ∖ N^{+} (x) ⊀ N^{+} (x) ∖ N^{-} (x)$ and hence $(V, \to, ≺)$ is not extendible by Lemma 2.9 .
Proof.
Let $a, b, c, d \in V$ be such that $a \to c$ , $b \to d$ , $a ∣ b$ , $c ∣ d$ , $a ≺ c$ , $d ≺ b$ and $\neg θ (a, b, c, d)$ . We fix $x \notin V$ and define an extension $\to^{'}$ of $(V, \to)$ to $V \cup {x}$ in stages, as an increasing union $\to^{'} = ⋃_{n \in N} \to_{n}$ . For each stage n, $\to_{n}$ is defined as follows:
$\to_{0}$ extends → by adding the edges $a \to x$ e $b \to x$ ;

$\to_{n + 1}$ extends $\to_{n}$ by adding edges $\begin{matrix} \{\begin{matrix} x \to_{n + 1} u & if \exists v ((x \to_{n} v \to u) \lor (u \to v \to_{n} x)) and either c \to u or d \to u; \\ u \to_{n + 1} x & if \exists v ((x \to_{n} v \to u) \lor (u \to v \to_{n} x)) and either u \to c or u \to d . \end{matrix} \end{matrix}$
Notice that $x \to^{'} u$ and $u \to^{'} x$ are incompatible, since if $c \to u$ or $d \to u$ then we have neither $u \to c$ nor $u \to d$ .

If we assume that $\to^{'}$ is pseudo-transitive we can complete the proof as follows. Since Φ and Ψ hold, by Lemma 3.7 we have $N (x) = N^{+} (x) \cup N^{-} (x)$ . On the other hand, by definition of $\to^{'}$ , $a -^{'} x -^{'} b$ but $x ∣^{'} c$ and $x ∣^{'} d$ (because $c ∣ d$ and hence we never set $x \to_{n + 1} c$ or $x \to_{n + 1} d$ ) and condition Λ fails. Thus, by Lemma 4.1.2, $N^{-} (x) ∖ N^{+} (x) ⊀ N^{+} (x) ∖ N^{-} (x)$ .

Therefore to complete the proof it suffices to check the pseudo-transitivity of $\to^{'}$ . We first make a few preliminary observations. Claim 4.10.1.
If $v \in V$ is such that $v \to^{'} x$ then either $v \to c$ or $v \to d$ . Similarly, if $u \in V$ is such that $x \to^{'} u$ then either $c \to u$ or $d \to u$ .
Proof.
Let n be least such that $v \to_{n} x$ . If $n = 0$ then v is either a or b, which satisfy the conclusion. If $n > 0$ then $v \to c$ or $v \to d$ is required by definition. When dealing with u, the case $n = 0$ cannot hold. □
Claim 4.10.2.
Let us assume that for $z, w \in V$ we have either $x \to^{'} z \to w$ or $w \to z \to^{'} x$ . Then if $w - c$ and $w ∣ d$ we have also $z - c$ and $z ∣ d$ , and similarly if $w - d$ and $w ∣ c$ we have also $z - d$ and $z ∣ c$ .
Proof.
Assume $w - c$ and $w ∣ d$ . If $x \to^{'} z \to w$ , then $c \to z$ or $d \to z$ by Claim 4.10.1. If $d \to z$ , then $d - w$ by $pt (z)$ , contrary to the assumption. So $c \to z$ , while $z \to d$ cannot hold because $c ∣ d$ . Thus we have $z - c$ and $z ∣ d$ . If $w \to z \to^{'} x$ the argument is similar.

The second statement is proved analogously. □
Claim 4.10.3.
$\forall e (e \neq a \land e \neq b \land e -_{1} x \Rightarrow e \to a \lor e \to b)$
Proof.
Let us suppose that $e \neq a$ , $e \neq b$ and $e -_{1} x$ , so that $e -_{0} x$ does not hold. The definition of $\to_{1}$ implies that for some v we have either $x \to_{0} v \to e$ or $e \to v \to_{0} x$ . Since the only v’s such that $v -_{0} x$ are a and b, and $a \to_{0} x$ and $b \to_{0} x$ , we must have the second possibility with v either a or b. □

In order to prove that $\to^{'}$ is pseudo-transitive, there are some cases to consider.
$v \to^{'} x \to^{'} u$ . By Claim 4.10.1 either $v \to c$ or $v \to d$ and also $c \to u$ or $d \to u$ . If either $v \to c \to u$ or $v \to d \to u$ , then $u - v$ follows by $pt (c)$ or $pt (d)$ of →.

We now concentrate on the case $v \to c$ and $d \to u$ , the other being similar. Notice that $c ∣ d$ implies that $u \to c$ and $d \to v$ do not hold. Moreover, we can assume that $v \to d$ and $c \to u$ both fail, else we are in one of the previous cases. Hence $u ∣ c$ and $v ∣ d$ . If n is the minimum stage such that $x \to_{n + 1} u$ (notice that $x \to_{0} u$ cannot happen), there exists $e_{n - 1}$ such that $x \to_{n} e_{n - 1} \to u$ or $u \to e_{n - 1} \to_{n} x$ . Analogously, there must be an $e_{n - 2}$ such that $x \to_{n - 1} e_{n - 2} \to e_{n - 1}$ or $e_{n - 1} \to e_{n - 2} \to_{n - 2} x$ . Iterating this procedure, we get to $x -_{1} e_{0}$ . Set also $e_{n} = u$ . Similarly, let k be least such that $v \to_{k} x$ (in this case $k = 0$ is possible) and set $h_{k} = v$ . If $k > 0$ , with a procedure similar to the one used before, we find $h_{0}, \dots, h_{k - 1}$ such that $h_{j}$ witnesses that $x -_{j + 1} h_{j + 1}$ for each $j < k$ .

Notice that a backward induction using Claim 4.10.2 easily entails both $\forall i < n (e_{i} - d \land e_{i} ∣ c)$ and $\forall j < k (h_{j} - c \land h_{j} ∣ d)$ . Notice also that for each $i < n$ either $d \to e_{i} \to e_{i + 1}$ or $e_{i + 1} \to e_{i} \to d$ holds. In fact, if $d \to e_{i}$ , then $x \to^{'} e_{i}$ by definition and so $e_{i} \to e_{i + 1}$ by choice of $e_{i}$ . If $e_{i} \to d$ the argument is similar. Arguing as in the previous lines it is easy to show that for each $j < k$ either $c \to h_{j} \to h_{j + 1}$ or $h_{j + 1} \to h_{j} \to c$ holds as well.

Let $i ⩽ n$ be least such that $d \to e_{i}$ . We claim that $e_{0}, \dots, e_{i}$ satisfy the first three conditions of $θ (a, b, c, d)$ :
$e_{0} \to b$ by Claim 4.10.3 because $e_{0} \to a$ implies $e_{0} - c$ by $pt (a)$ , which contradicts the above observation;

$\forall j < i (e_{j + 1} \to e_{j} \to d)$ : this is immediate by the minimality of i and the observation in the previous paragraph;

$d \to e_{i}$ by choice of i;
Since $θ (a, b, c, d)$ fails, condition ( $θ_{4}$ ) must fail, i.e. we have $e_{i} - a$ .

Since $a ∣ d$ we can apply Property 3.6 to obtain that $e_{j} - a$ for every $j ⩽ n$ with $j ⩾ i$ . Recalling that $e_{n} = u$ , we obtained $u - a$ : then $a \to u$ because $a ∣ d$ .

We show that $h_{j} - u$ for every $j ⩽ k$ . Arguing as in the proof of ( $θ_{1}$ ) above, we have $h_{0} \to a$ so that $h_{0} - u$ by $pt (a)$ . Thus, since $u ∣ c$ , we can apply Property 3.6 again to obtain the desired conclusion. Recalling that $h_{k} = v$ we have obtained $u - v$ .

$x \to^{'} v \to u$ then $c \to v$ or $d \to v$ by Claim 4.10.1. By $pt (v)$ , either $c - u$ or $d - u$ and u satisfies one of the conditions in the definition of $\to^{'}$ . Thus $x -^{'} u$ .

$u \to v \to^{'} x$ is similar to the previous item.
This shows that $\to^{'}$ is pseudo-transitive and hence that $(V, \to, ≺)$ is not extendible. □

Summarizing, we obtained a characterization of the conditions of Lemma 2.9.
Theorem 4.11.
Let $(V, \to, ≺)$ be a GH-triple. The following are equivalent:
for each pseudo-transitive extension $(V \cup {x}, \to^{'})$ of $(V, \to)$ we have both $N (x) = N^{+} (x) \cup N^{-} (x)$ and $N^{-} (x) ∖ N^{+} (x) ≺ N^{+} (x) ∖ N^{-} (x))$ ;

Φ, Ψ and Θ are satisfied.

Proof.
The implication (1) ⇒ (2) follows from Lemmas 3.8 and 4.10. The implication (2) ⇒ (1) follows from Lemmas 3.7 and 4.9. □

Thanks to Theorem 4.11 we can now reformulate Lemma 2.9 in a way that does not refer to all possible pseudo-transitive extensions of $(V, \to)$ but mentions only structural properties of $(V, \to)$ and ≺.
Theorem 4.12.
Let $(V, \to, ≺)$ be an extendible GH-triple. Then Φ, Ψ and Θ are satisfied.

It follows from Lemma 5.13 below that the reverse implication holds as well, namely that Φ, Ψ and Θ are also sufficient conditions of the extendibility of a GH-triple.
5. The smart extension algorithm

In this section we define an on-line algorithm to transitively reorient a countable pseudo-transitive ograph. Before defining the algorithm we give some preliminary definitions.

Definition 5.1.

Let $(V, \to, ≺)$ be a GH-triple. If $(V \cup {x}, \to^{'})$ is a pseudo-transitive extension of →, we define inductively the following subsets of $N (x)$ : $\begin{array}{l} S_{0}^{-} (x) = N^{-} (x) ∖ N^{+} (x); \\ S_{0}^{+} (x) = N^{+} (x) ∖ N^{-} (x); \\ S_{i} (x) = S_{i}^{-} (x) \cup S_{i}^{+} (x); \\ S_{i + 1}^{-} (x) = {a \in N (x) ∖ ⋃_{j ⩽ i} S_{j} (x) | \exists s \in S_{i}^{-} (x) (a ∣ s)}; \\ S_{i + 1}^{+} (x) = {a \in N (x) ∖ ⋃_{j ⩽ i} S_{j} (x) | \exists s \in S_{i}^{+} (x) (a ∣ s)} . \end{array}$ Let $S^{+} (x) = ⋃_{i \in N} S_{i}^{+} (x)$ , $S^{-} (x) = ⋃_{i \in N} S_{i}^{-} (x)$ and $S (x) = S^{-} (x) \cup S^{+} (x) = ⋃_{i \in N} S_{i} (x)$ . Let also $T (x) = N (x) ∖ S (x)$ .

If $* \in {+, -}$ we say that a sequence $ρ = ⟨ ρ (0), ρ (1), \dots, ρ (| ρ | - 1) ⟩$ of elements of V is a ∗-sequence if $ρ (i) \in S_{i}^{*} (x)$ for every $i < | ρ |$ and $ρ (i) ∣ ρ (i + 1)$ for every $i < | ρ | - 1$ .

Remark 5.2.

If $N (x) = N^{+} (x) \cup N^{-} (x)$ then $S (x) ∖ S_{0} (x)$ and $T (x)$ are both included in $N^{+} (x) \cap N^{-} (x)$ . Moreover $S (x) \subseteq N (t)$ for every $t \in T (x)$ (because if $t \in N (x)$ and $S_{i} (x) ∖ N (t) \neq \emptyset$ then $t \in S_{i + 1} (x)$ ).

Notice that if $s \in S_{i}^{*} (x)$ then there exists a ∗-sequence ρ such that $ρ (i) = s$ .

For the remainder of the section we use $S^{*} (x)$ as a shorthand for either $S^{+} (x)$ or $S^{-} (x)$ . $S_{i}^{*} (x)$ is used similarly and $s_{i}^{*}$ always denotes an element of $S_{i}^{*} (x)$ . We now prove some properties of $S^{*} (x)$ and its subsets.

Property 5.3.

Let $(V, \to, ≺)$ be a GH-triple. Let $(V \cup {x}, \to^{'})$ be a pseudo-transitive extension of →.

Fix $v \in V \cup {x}$ and $* \in {+, -}$ . If ρ is a ∗-sequence such that $\forall i < | ρ | (v -^{'} ρ (i))$ then we have either $\forall i < | ρ | (ρ (i) \to^{'} v)$ or $\forall i < | ρ | (v \to^{'} ρ (i))$ .

$S^{-} (x) ≺ T (x)$ and $T (x) ≺ S^{+} (x)$ .

If $ρ^{*}$ is a ∗-sequence for $* \in {+, -}$ , $ρ^{+} (0) \to^{'} x \leftarrow^{'} ρ^{-} (0)$ and $e_{0}, \dots, e_{n}$ witness $φ (ρ^{-} (0), ρ^{+} (0), f)$ for some $f ∣^{'} x$ , then there exists $i ⩽ n$ such that $e_{i}, \dots, e_{n}$ witness $φ (ρ^{-} (k), ρ^{+} (j), x)$ , for each k and j. Moreover, $ρ^{-} (k) \to^{'} x \leftarrow^{'} ρ^{+} (j)$ . The same statement holds with ψ in place of φ.

Proof.

(1) is obvious by pseudo-transitivity of $\to^{'}$ .

To prove (2) we fix $t \in T (x)$ and prove by induction on i that $t ≺ S_{i}^{+} (x)$ for every i. For the base of the induction, $t ≺ S_{0}^{+} (x)$ follows from $S_{0}^{+} (x) \subseteq N (t)$ (Remark 5.2), $t \in N^{-} (x)$ and $S_{0}^{+} (x) \cap N^{-} (x) = \emptyset$ . For the induction step let $s_{i + 1}^{+} \in S_{i + 1}^{+} (x)$ and choose $s_{i}^{+} \in S_{i}^{+} (x)$ such that $s_{i + 1}^{+} ∣ s_{i}^{+}$ . By induction hypothesis $t ≺ s_{i}^{+}$ and hence, since $s_{i + 1}^{+} - t$ (again by Remark 5.2), we have $t ≺ s_{i + 1}^{+}$ . This shows $T (x) ≺ S^{+} (x)$ . Analogously we prove $S^{-} (x) ≺ T (x)$ .

To prove (3) fix $ρ^{+}$ , $ρ^{-}$ , f, $e_{0}, \dots, e_{n}$ satisfying the hypothesis. Let $m^{*}$ be the length of $ρ^{*}$ for $* \in {+, -}$ . We write $s_{k}^{*}$ in place of $ρ^{*} (k)$ . Since $s_{0}^{*} \to^{'} x$ and $S (x) \subseteq N (x)$ , (1) implies that $s_{k}^{*} \to^{'} x$ for each $k < m^{*}$ .

Applying Property 3.5 to $(V \cup {x}, \to^{'})$ we obtain that there exists $i ⩽ n$ such that $e_{i}, \dots, e_{n}$ witness $φ (s_{0}^{-}, s_{0}^{+}, x)$ . For the sake of convenience assume $i = 0$ , so that $e_{0}, \dots, e_{n}$ witness $φ (s_{0}^{-}, s_{0}^{+}, x)$ as well.

Fix $* \in {+, -}$ . We claim that $\forall k < m^{*} \forall i ⩽ n (e_{i} - s_{k}^{*})$ . The proof is by double induction.2

Since we are dealing with formulas where all quantifiers are bounded, this can be done within ${RCA}_{0}$ .

Suppose

\forall i ⩽ n (e_{i} - s_{ℓ}^{*})

for each

ℓ < k

. We prove by induction on i that

\forall i ⩽ n (e_{i} - s_{k}^{*})

. For the base case,

e_{0} - s_{k}^{*}

pt (x)

since

s_{k}^{*} \to^{'} x

and

x \to^{'} e_{0}

by (

φ_{1}

) of

φ (s_{0}^{-}, s_{0}^{+}, x)

. For the induction step suppose

e_{i} - s_{k}^{*}

. If

s_{k}^{*} \to e_{i}

, then

s_{0}^{*} \to e_{i}

by (1) (that applies because

\forall ℓ < k (e_{i} - s_{ℓ}^{*})

). Then

e_{i} \to e_{i + 1}

φ (s_{0}^{-}, s_{0}^{+}, x)

. Hence

e_{i + 1} - s_{k}^{*}

pt (e_{i})

. If

e_{i} \to s_{k}^{*}

, the argument is analogous.

Let $k < m^{-}$ and $j < m^{+}$ . We check that the three conditions of $φ (s_{k}^{-}, s_{j}^{+}, x)$ are satisfied. Condition ( $φ_{1}$ ) holds trivially since it coincides with ( $φ_{1}$ ) of $φ (s_{0}^{-}, s_{0}^{+}, x)$ . To check that ( $φ_{2}$ ) holds suppose $s_{k}^{-} \to e_{i}$ . Then $s_{0}^{-} \to e_{i}$ by (1) and thus $s_{0}^{+} \to e_{i} \to e_{i + 1}$ by ( $φ_{2}$ ) of $φ (s_{0}^{-}, s_{0}^{+}, x)$ . By (1) again it holds that $s_{j}^{+} \to e_{i}$ holds as well. An analogous argument shows that if $e_{i} \to s_{k}^{-}$ , then $e_{i + 1} \to e_{i} \to s_{j}^{+}$ . These establish that ( $φ_{2}$ ) of $φ (s_{k}^{-}, s_{j}^{+}, x)$ holds. Condition ( $φ_{3}$ ) is checked in a similar way. □

Notice that Property 5.3.2 implies $S^{-} (x) ≺ S^{+} (x)$ whenever $T (x) \neq \emptyset$ . To see that this holds in general we need to strengthen the hypothesis on the reorientation of $(V, \to)$ .

Lemma 5.4.

Let $(V, \to, ≺)$ be a GH-triple such that Ψ, Φ and Θ are satisfied. Let $(V \cup {x}, \to^{'})$ be a pseudo-transitive extension of →. Then $S^{-} (x) ≺ S^{+} (x)$ and hence $S^{-} (x) \cap S^{+} (x) = \emptyset$ .

Proof.

Let $s^{-} \in S^{-} (x)$ . We first claim that $s^{-} - s^{+}$ for every $s^{+} \in S^{+} (x)$ , which is obviously necessary for $S^{-} (x) ≺ S^{+} (x)$ . Since $s^{-}, s^{+} \in N (x)$ , there are four possibilities.

If $s^{+} \to^{'} x \to^{'} s^{-}$ or $s^{-} \to^{'} x \to^{'} s^{+}$ , then by $pt (x)$ we have $s^{-} - s^{+}$ .

Otherwise, $s^{-} \to^{'} x \leftarrow^{'} s^{+}$ or $s^{+} \leftarrow^{'} x \to^{'} s^{-}$ . Suppose the former holds. For $* \in {+, -}$ choose a ∗-sequence $⟨ s_{0}^{*}, \dots, s_{m^{*}}^{*} ⟩$ such that $s_{m^{*}}^{*} = s^{*}$ . Recall that, by definition of ∗-sequence, $s_{i}^{*} \in S_{i}^{*} (x)$ for each $i ⩽ m^{*}$ and $s_{i}^{*} ∣ s_{i + 1}^{*}$ for each $i < m^{*}$ .

Since $s^{-} \to^{'} x \leftarrow^{'} s^{+}$ , Property 5.3.1 implies that $s_{0}^{+} \to^{'} x \leftarrow^{'} s_{0}^{-}$ . Since $s_{0}^{+} \notin N^{-} (x)$ , there exists f such that $f ≺ s_{0}^{+}$ and $f ∣^{'} x$ . Analogously, there exists e such that $s_{0}^{-} ≺ e$ and $e ∣^{'} x$ . Given that $f ∣^{'} x ∣^{'} e$ and $s_{0}^{+} \to^{'} x \leftarrow^{'} s_{0}^{-}$ , then $s_{0}^{+} \to f$ and $s_{0}^{-} \to e$ . Moreover, since $s_{0}^{-} ≺ s_{0}^{+}$ by Theorem 4.11, it holds $s_{0}^{+} \to s_{0}^{-}$ or $s_{0}^{-} \to s_{0}^{+}$ . Suppose the latter, the other case being similar using e in place of f. We have $s_{0}^{-} - f$ by $pt (s_{0}^{+})$ , and thus $s_{0}^{-} \to f$ since $s_{0}^{-} \to^{'} x$ and $x ∣^{'} f$ . Since $s_{0}^{-} \in N^{-} (x)$ , then $s_{0}^{-} ≺ f$ . Summarizing, we have just shown that $s_{0}^{-} ≺ f ≺ s_{0}^{+}$ and $s_{0}^{+} \to f \leftarrow s_{0}^{-}$ . Since we are assuming Φ holds, there are $e_{0}, \dots, e_{n}$ witnessing $φ (s_{0}^{-}, s_{0}^{+}, f)$ . Applying Property 5.3.3 we obtain that there exists an $i ⩽ n$ such that $e_{i}, \dots, e_{n}$ witness $φ (s_{k}^{-}, s_{j}^{+}, x)$ for each $k ⩽ m^{+}$ and $j ⩽ m^{-}$ . In particular $φ (s^{-}, s^{+}, x)$ is satisfied and so either $s^{-} \to e_{n} \to s^{+}$ or $s^{+} \to e_{n} \to s^{-}$ holds. In both cases, by $pt (e_{n})$ , $s^{+} - s^{-}$ as we wanted to show.

If instead $s^{-} \leftarrow^{'} x \to^{'} s^{+}$ the argument is similar, reversing all arrows and using Ψ.

We have thus established our claim that $s^{-} - s^{+}$ for every $s^{+} \in S^{+} (x)$ . Now we prove by induction on i that $s^{-} ≺ S_{i}^{+} (x)$ for every i. For the base of the induction, $s^{-} ≺ s_{0}^{+}$ for every $s_{0}^{+} \in S_{0}^{+} (x)$ because $s^{-} - s_{0}^{+}$ , $s^{-} \in N^{-} (x)$ and $s_{0}^{+} (x) \notin N^{-} (x)$ . For the induction step let $s_{i + 1}^{+} \in S_{i + 1}^{+} (x)$ and choose $s_{i}^{+} \in S_{i}^{+} (x)$ such that $s_{i + 1}^{+} ∣ s_{i}^{+}$ . By induction hypothesis $s^{-} ≺ s_{i}^{+}$ and hence, since $s_{i + 1}^{+} - s^{-}$ , we have $s^{-} ≺ s_{i + 1}^{+}$ . □

These relations between subsets of $N (x)$ explain the choices for the reorientation of $V \cup {x}$ made in the following definition.

Definition 5.5.

Let $(V, \to, ≺)$ be a GH-triple satisfying Φ, Ψ and Θ and such that $V \subseteq N$ . Let $(V \cup {x}, \to^{'})$ be a pseudo-transitive extension of →.

We define $≺^{'}$ , the smart extension of ≺ to $(V \cup {x}, \to^{'})$ , as the binary relation that extends ≺ to $V \cup {x}$ by establishing the relationship between x and each $v \in V$ recursively as follows:

if $v \notin N (x)$ let $v ⊀^{'} x$ and $x ⊁^{'} v$ ;

if $v \in S (x)$ then

if $v \in S^{-} (x)$ let $v ≺^{'} x$ ,

if $v \in S^{+} (x)$ let $x ≺^{'} v$ ;

if $v \in T (x)$ then

if there exists $u < v$ such that $v ≺ u ≺^{'} x$ let $v ≺^{'} x$ ,

if there exists $u < v$ such that $x ≺^{'} u ≺ v$ let $x ≺^{'} v$ ,

otherwise let $v ≺^{'} x$ if $v \to^{'} x$ and $x ≺^{'} v$ if $x \to^{'} v$ .

Notice that $≺^{'}$ depends on the order < on $N$ , is always a reorientation of $(V \cup {x}, \to^{'})$ , and extends ≺.

For a visual understanding of $≺^{'}$ see Fig. 4. Here we denote by $T^{-} (x)$ , resp. $T^{+} (x)$ , the subset of $T (x)$ consisting of the vertices which are below, resp. above, x. Moreover the picture shows that $S_{i}^{-} (x) ≺ S_{i + 2}^{-} (x)$ and $S_{i + 2}^{+} (x) ≺ S_{i}^{+} (x)$ : we leave to the reader to prove these relations, since we do not need them. The picture may suggest that $(N (x), ≺)$ has width two, but this is not the case because there may be nontrivial antichains within some $S_{i}^{*} (x)$ and/or $T^{*} (x)$ .

Figure 4.

A smart extension.

The hypothesis that $(V, \to, ≺)$ satisfies Φ, Ψ and Θ makes sure that Conditions (2a) and (2b) of Definition 5.5 are mutually exclusive, by Lemma 5.4. Some of the clauses of Definition 5.5 are necessary for $≺^{'}$ to be a transitive reorientation of $\to^{'}$ . Condition (1) is obviously necessary for $≺^{'}$ to be a reorientation. The choice $S^{-} (x) ≺ x$ made by Condition (2a) is explained by an inductive argument: $S_{0}^{-} (x) ≺^{'} x$ is required because $S_{0}^{-} (x) \cap N^{+} (x) = \emptyset$ , and if $S_{i}^{-} (x) ≺ x$ then the members of $S_{i + 1}^{-} (x)$ (each incomparable with some element of $S_{i}^{-} (x)$ ) cannot lie above x. The same argument applies to $S^{+} (x)$ and justifies Condition (2b). Conditions (3a) and (3b) are clearly necessary for transitivity. Condition (3c) is applied when the relationship between x and $v_{i}$ is not decided by the previous conditions and in this case $≺^{'}$ simply preserves the direction of $\to^{'}$ .

From a complexity point of view, defining the sets $S^{+} (x)$ and $S^{-} (x)$ requires more resources than setting the relation between x and $v \in V$ according to Definition 5.5. The sets $S_{0}^{+} (x)$ and $S_{0}^{-} (x)$ are computed in at most $| V^{2} |$ steps, since one needs to consider each $v \in N (x)$ and for each such v to go through each $u \in N (v) ∖ N (x)$ . The remaining members of $S^{+} (x)$ and $S^{-} (x)$ can be found by a depth-first search algorithm applied to the non-adjacency graph $(V \cup {x}, E^{'})$ (the complexity of depth-first search algorithm is $O (| V | + | E |)$ , see [4, Section 22.3]). To this end notice that for each $s_{0} \in S_{0}^{+} (x)$ there exists a sequence3

Such sequences may not be +-sequences, because it may be the case that $v_{i} \in S_{j}^{+} (x)$ , for some $j < i$ due to the incomparability chain caused by some other element of $S_{0}^{+} (x)$ .

v_{0} = s_{0}, v_{1}, \dots, v_{n}

, for some

n < | V |

, such that

v_{i} E^{'} v_{i + 1}

and

v_{i} \in N (x)

, for each

i ⩽ n

. Then each

v_{i} \in S^{+} (x)

. The same obviously applies also to

S^{-} (x)

Therefore an upper bound for the complexity of the smart extension is $O (| V |^{2})$ .

Definition 5.6.

Let $(V, \to)$ be a pseudo-transitive ograph with V an initial interval of $N$ . The relation ≺ is the smart reorientation of → if it at each step s the reorientation $≺_{s + 1} = ≺ ↾ {0, \dots, s}$ is obtained as the smart extension of $≺_{s}$ .

Remark 5.7.

Notice that the smart reorientation of $(V, \leftarrow)$ is the reversal of the smart reorientation of $(V, \to)$ .

Theorem 5.14 proves that the smart reorientation algorithm is correct. To obtain this result we prove some properties of smart reorientations. In particular we introduce the notion of ‘lazy reorientation’ in Definition 5.9. The intuitive idea behind it is the following one: an edge $a \to b$ is reversed only when this is really needed to obtain a transitive reorientation, because $a \to b \to c \to a$ and the edges $b \to c$ and $c \to a$ are not reversed.

Property 5.8.

Let $(V, \to, ≺)$ be a GH-triple with $V \subseteq N$ . Let $(V \cup {x}, \to^{'})$ be a pseudo-transitive extension of →. Let $≺^{'}$ be the smart extension of ≺.

If $a ≺^{'} x$ because we applied condition (3a) with witness b then $b \in T (x)$ . Moreover we can choose b so that $b \to^{'} x$ .

Similarly, if $x ≺^{'} a$ because we applied condition (3b) with witness b then $b \in T (x)$ and we can assume $x \to^{'} b$ .

Proof.

Let $a \in T (x)$ and b with $b < a$ be such that $a ≺ b ≺^{'} x$ . Since $b ≺^{'} x$ then $b \in S^{-} (x) \cup T (x)$ . But $b \notin S^{-} (x)$ by Property 5.3.2 and hence $b \in T (x)$ . Let b be least (as a natural number) such that $a ≺ b ≺^{'} x$ . If $x \to^{'} b$ , then we used condition (3a) when dealing with b and so there exists $c < b$ such that $b ≺ c ≺^{'} x$ , contrary to the minimality of b. Hence, $b \to^{'} x$ .

The proof of the second statement is analogous. □

Definition 5.9.

Let $(V, \to)$ be a pseudo-transitive ograph. The reorientation ≺ of → is a lazy reorientation if it satisfies the following property: for each $a, b \in V$ such that $a \to b$ and $b ≺ a$ there exists $c \in V$ such that $b \to c \to a$ (i.e. $a b c$ is a non transitive triangle), $b ≺ c ≺ a$ , and $c < min (a, b)$ .

$(V, \to, ≺)$ is a lazy triple if $(V, \to)$ is a pseudo-transitive ograph and the reorientation ≺ of → is a lazy reorientation.

Notice that a lazy triple is not necessarily a GH-triple, because we are not requiring ≺ to be transitive.

Remark 5.10.

$(V, \to, ≺)$ is a lazy triple if only if $(V, \leftarrow, ≻)$ is a lazy triple, where $(V, \leftarrow)$ is the reverse ograph of $(V, \to)$ .

Property 5.11.

Let $(V, \to)$ be a pseudo-transitive ograph with $V \subseteq N$ and let ≺ be the smart reorientation of $(V, \to)$ . Assume that ≺ is transitive, so that $(V, \to, ≺)$ is a GH-triple. Then ≺ is lazy, i.e. $(V, \to, ≺)$ is a lazy triple.

Proof.

The proof of the laziness condition for every $a, b \in V$ is by induction on the lexicographic order of the pair of natural numbers $(max (a, b), min (a, b))$ . Suppose $a \to b$ and $b ≺ a$ and assume that for each $a^{'}$ and $b^{'}$ such that $a^{'} \to b^{'}$ , $b^{'} ≺ a^{'}$ and either $max (a^{'}, b^{'}) < max (a, b)$ or $max (a^{'}, b^{'}) = max (a, b)$ and $min (a^{'}, b^{'}) < min (a, b)$ there exists $c^{'}$ such that $b^{'} \to c^{'} \to a^{'}$ , $b^{'} ≺ c^{'} ≺ a^{'}$ , and $c^{'} < min (a^{'}, b^{'})$ .

By remark 5.7 we can assume without loss of generality that $a < b$ . According to Definition 5.5 either $a \in S^{+} (b)$ or $a \in T (b)$ .

If $a \in S^{+} (b)$ let i be such that $a \in S_{i}^{+} (b)$ . We first show that $i > 0$ is impossible. If $a \in S_{i}^{+} (b)$ with $i > 0$ let ρ be a +-sequence of length at least 2 such that $ρ (i) = a$ . By Property 5.3.1 we have $ρ (1) \to b$ . Since $ρ (1) \in S_{1}^{+} (b)$ , there exists $d < b$ such that $d \in S_{0}^{+} (b)$ and $d ∣ ρ (1)$ . Then $b ≺ d$ and $d \to b$ . Since $d \in S_{0}^{+} (b)$ there exists $f < b$ , $f ∣ b$ , $f ≺ d$ . Thus $d \to f$ . As $max (d, f) < b = max (a, b)$ we can apply the induction hypothesis and there exists c such that $f \to c \to d$ and $f ≺ c ≺ d$ . We have $c - b$ by $pt (d)$ , and hence $b \to c$ because $b ∣ f$ . But now $ρ (1) - c$ by $pt (b)$ , and hence $c \to ρ (1)$ since $ρ (1) ∣ d$ . Using again $pt (c)$ we have $ρ (1) - f$ , a contradiction with $ρ (1) \in S_{1}^{+} (b) \subseteq N^{-} (b) \cap N^{+} (b)$ as $f \notin N (b)$ .

Thus $i = 0$ and $a \notin N^{-} (b)$ . In particular there exists $f < b$ , $f ∣ b$ , $f ≺ a$ and so $a \to f$ . As $max (a, f) < max (a, b)$ we can apply the induction hypothesis and there exists $c < min (a, f)$ such that $f \to c \to a$ and $f ≺ c ≺ a$ . We have $c - b$ by $pt (a)$ , and hence $b \to c$ because $b ∣ f$ . Hence $b \to c \to a$ , $b ≺ c ≺ a$ (because ≺ is transitive and $b ∣ f$ ), and $c < min (a, b)$ , as required.

If $a \in T (b)$ we applied condition (3b) of Definition 5.5 to set $b ≺ a$ . Hence, by Property 5.8 there exists c such that $c < a$ , $b ≺ c ≺ a$ and $b \to c$ . We can assume that c is least (as a natural number) with these properties. If $c \to a$ we have our conclusion. We now rule out the possibility that $a \to c$ . If this was the case, by induction hypothesis (as $max (a, c) < max (a, b)$ ) there exists $d < min (a, c)$ such that $c \to d \to a$ and $c ≺ d ≺ a$ . By transitivity of ≺ we have $b ≺ d ≺ a$ and $b - d$ . If $b \to d$ then $d < c$ violates the minimality of c. If $d \to b$ then by induction hypothesis (as $max (d, b) = max (a, b)$ and $min (d, b) < min (a, b)$ ) there exists $e < d$ such that $b ≺ e ≺ d$ and $b \to e \to d$ . But then $e < c$ , $b ≺ e ≺ a$ (by transitivity of ≺) and $b \to e$ contradict the minimality of c. □

Lemma 5.12.

Let $(V, \to, ≺)$ be a GH-triple which is also a lazy triple and such that $V \subseteq N$ . Then Φ, Ψ and Θ are satisfied.

Proof.

Thanks to laziness checking that Θ holds is straightforward. In fact, suppose $a \to c$ , $b \to d$ , $a ≺ c$ and $d ≺ b$ for some $a, b, c, d \in V$ . Since $b \to d$ but $d ≺ b$ , there exists an $e_{0}$ such that $d \to e_{0} \to b$ . It is immediate to check that $e_{0}$ witnesses $θ (a, b, c, d)$ .4

⁴

Notice that laziness implies a strong form of Θ, in fact the sequence witnessing the formulas have always length one.

To check that Φ holds let $a, b, c \in V$ be such that $a \to c \leftarrow b$ and $a ≺ c ≺ b$ . Since $b \to c$ , $c ≺ b$ and ≺ is lazy, there exists $e_{0} \in V$ such that $c \to e_{0} \to b$ , $c ≺ e_{0} ≺ b$ and $e_{0} < min (b, c)$ . By transitivity of ≺ it follows that $a ≺ e_{0}$ and thus $a - e_{0}$ , since ≺ is a reorientation. If $a \to e_{0}$ , it is immediate to check that $e_{0}$ witnesses $φ (a, b, c)$ .

Otherwise $e_{0} \to a$ and, since $a ≺ e_{0}$ , by laziness there exists $e_{1} \in V$ such that $a \to e_{1} \to e_{0}$ , $a ≺ e_{1} ≺ e_{0}$ and $e_{1} < min (e_{0}, a)$ . Notice that even if $a \to c \to e_{0}$ and $a ≺ c ≺ e_{0}$ it must be $c \neq e_{1}$ because $e_{1} < e_{0} < c$ by construction. By transitivity we get that $e_{1} ≺ b$ and so either $e_{1} \to b$ or $b \to e_{1}$ . If the former holds then $e_{0}$ , $e_{1}$ witness $φ (a, b, c)$ .

We have now to analyze the case when $b \to e_{1}$ . Since $e_{1} ≺ b$ by laziness there exists $e_{2}$ such that $e_{1} \to e_{2} \to b$ , $e_{1} ≺ e_{2} ≺ b$ and $e_{2} < min (b, e_{1})$ . By transitivity it holds that $a ≺ e_{2}$ . If $a \to e_{2}$ , it is easy to check that $e_{0}$ , $e_{1}$ , $e_{2}$ witness $φ (a, b, c)$ . Otherwise $e_{2} \to a$ and we can apply laziness again to obtain $e_{3}$ .

This procedure provides a <-decreasing sequence $(e_{i})$ such that $a \to e_{i + 1} \to e_{i}$ when i is even, and $e_{i} \to e_{i + 1} \to b$ when i is odd. The sequence stops with $e_{n}$ such that $a \to e_{n} \to b$ . We claim that $e_{0}, \dots, e_{n}$ witness $φ (a, b, c)$ . In fact ( $φ_{1}$ ) is guaranteed by $c \to e_{0}$ . Moreover, for each $i < n$ either $a \to e_{i} \leftarrow b$ or $a \leftarrow e_{i} \to b$ by assumption. If the former is the case then $e_{i} \to e_{i + 1}$ , while if the latter holds $e_{i + 1} \to e_{i}$ by construction. These two facts guarantee that ( $φ_{2}$ ) is satisfied as well. The vertex $e_{n}$ satisfies condition ( $φ_{3}$ ) by construction.

It is now easy to check that Ψ is satisfied as well applying the duality principle of Remark 3.4. Consider the graph $(V, \leftarrow)$ and the transitive reorientation ≻. Remark 5.10 guarantees that ≻ is lazy as well. Hence, Φ holds by what we have just shown. Then, by Remark 3.4, Ψ holds in $(V, \to)$ and ≺. □

Lemma 5.13.

Let $(V, \to, ≺)$ be a GH-triple such that $V \subseteq N$ . Assume Φ, Ψ and Θ are satisfied. Let $(V \cup {x}, \to^{'})$ be a pseudo-transitive extension of $(V, \to)$ . Then the smart extension $≺^{'}$ to $\to^{'}$ is transitive.

Proof.

To check that ≺ is transitive, we have to consider the following cases, where $a, b \in V$ :

$a ≺^{'} x ≺^{'} b$ . Obviously $a, b \in N (x)$ and, if $a \in S (x)$ then $a \in S^{-} (x)$ while if $b \in S (x)$ then $b \in S^{+} (x)$ . We consider four possibilities:

$a \in S^{-} (x)$ , $b \in S^{+} (x)$ : then $a ≺ b$ follows from Lemma 5.4.

$a, b \in T (x)$ : if $a \to^{'} x \to^{'} b$ or $b \to^{'} x \to^{'} a$ , then $a - b$ by pseudo-transitivity. So we are left to check that $b ⊀ a$ . Suppose $b ≺ a$ . Then, according to the definition of $≺^{'}$ , if $b < a$ , then $x ≺^{'} b$ entails $x ≺^{'} a$ , while if $a < b$ , then $a ≺^{'} x$ entails $b ≺^{'} x$ .

Otherwise, $a \to^{'} x \leftarrow^{'} b$ or $a \leftarrow^{'} x \to^{'} b$ . Suppose the latter holds, the former being similar. Since $x \to^{'} a$ , but $a ≺^{'} x$ by assumption, there is, by Property 5.8, $c < a$ such that $c \in T (x)$ , $c \to^{'} x$ and $a ≺ c ≺^{'} x$ . Notice that $c - b$ by $pt (x)$ . We claim that $b ⊀ c$ . Suppose $b ≺ c$ . If $c < b$ , then, since $b ≺ c ≺^{'} x$ , then $b ≺^{'} x$ by definition, contrary to the assumption. Otherwise, $b < c$ ; then, since $x ≺^{'} b ≺ c$ , then $x ≺^{'} c$ , contrary to the assumption. Thus it must be $c ≺ b$ and so $a ≺ b$ because ≺ is transitive by hypothesis.

$a \in S^{-} (x)$ , $b \in T (x)$ : $a ≺ b$ follows by Property 5.3.2.

$a \in T (x)$ , $b \in S^{+} (x)$ : $a ≺ b$ follows by Property 5.3.2.

$a ≺ b ≺^{'} x$ . Since $b \in S^{-} (x) \cup T (x)$ we have $b \in N^{-} (x)$ and thus $a \in N (x)$ . If $a \in S (x)$ , Property 5.3.2 or Lemma 5.4 imply $a \in S^{-} (x)$ , and thus $a ≺^{'} x$ .

If instead $a \in T (x)$ then $b \in T (x)$ by Property 5.3.2. If $b < a$ then $a ≺ b ≺^{'} x$ implies $a ≺^{'} x$ . If $a < b$ then $x ≺^{'} a$ would imply $x ≺^{'} b$ ; hence $a ≺^{'} x$ holds also in this case.

$x ≺^{'} a ≺ b$ . The argument is similar to the previous case.

□

The following theorem proves that Definition 5.5 provides an algorithm to transitively reorient pseudo-transitive graphs.

Theorem 5.14.

Let $(V, \to)$ be a pseudo-transitive ograph with V an initial interval of $N$ and let ≺ be the smart reorientation of $(V, \to)$ . Then ≺ is transitive.

Proof.

For each $s \in N$ , let $≺_{s}$ be the restriction of ≺ to ${0, \dots, s - 1}$ . Notice that $≺_{s}$ is the smart reorientation of the restriction of → to ${0, \dots, s - 1}$ . To prove that ≺ is transitive it is enough to check that $≺_{s}$ is transitive for each s. We do so by induction on s. For the base case there is nothing to check. Suppose $≺_{s}$ is transitive. Then by Property 5.11 $≺_{s}$ is lazy. Moreover, by Lemma 5.12 Φ, Ψ and Θ are satisfied. Hence, by Lemma 5.13 the smart extension $≺_{s + 1}$ is transitive. □

Footnotes

Acknowledgements

We thank Nicola Gigante and Paul Shafer for useful discussions about the topic of the paper.

Both author’s research was partially supported by the departmental PRID funding “HiWei – The higher levels of the Weihrauch hierarchy”.

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.

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

Abstract

Keywords

1. Introduction

1 Further results were obtained by Gallai [6].

Footnotes

Acknowledgements

References

¹
Further results were obtained by Gallai [6].