Bi-Arc Digraphs and Conservative Polymorphisms

arXiv:1608.03368v3 [] 29 Dec 2016

Pavol Hell

∗

Arash Rafiey

†

Abstract
We introduce the class of bi-arc digraphs, and show they coincide with the class of digraphs
that admit a conservative semi-lattice polymorphism, i.e., a min ordering. Surprisingly this turns
out to be also the class of digraphs that admit totally symmetric conservative polymorphisms
of all arities. We give an obstruction characterization of, and a polynomial time recognition
algorithm for, this class of digraphs. The existence of a polynomial time algorithm was an open
problem due to Bagan, Durand, Filiot, and Gauwin.
We also discuss a generalization to k-arc digraphs, which has a similar obstruction characterization and recognition algorithm.
When restricted to undirected graphs, the class of bi-arc digraphs is included in the previously
studied class of bi-arc graphs. In particular, restricted to reflexive graphs, bi-arc digraphs
coincide precisely with the well known class of interval graphs. Restricted to reflexive digraphs,
they coincide precisely with the class of adjusted interval digraphs, and restricted to bigraphs,
they coincide precisely with the class of two directional ray graphs. All these classes have been
previously investigated as analogues of interval graphs. We believe that, in a certain sense,
bi-arc digraphs are the most general digraph version of interval graphs with nice algorithms and
characterizations.

1 Introduction
In this paper we investigate a class of digraphs that can be viewed as a digraph generalization
of interval graphs. A graph H is an interval graph if it is the intersection graph of a family of
intervals on the real line, i.e., if there exist intervals Iv , v ∈ V (H), such that uv ∈ A(H) if and only
if Iu ∩ Iv 6= ∅.
Interval graphs are one of the most popular and useful graph classes; they admit efficient
recognition algorithms, elegant obstruction characterizations, and frequently occur in practice
[4, 6, 16, 17, 18, 30]. The classical digraph versions of interval graphs [35] lack many of these
desirable attributes, although the authors have (in an paper joint with T. Feder and J. Huang)
proposed a version of interval digraphs that shares with interval graphs many nice properties; that
version only applies to reflexive digraphs (that is, digraphs in which every vertex has a loop) [12].
∗

Simon Fraser University, BC, Canada, pavol@sfu.ca; this work was partially supported by NSERC (Canada) and
by ERCCZ LL 1201 Cores (Czech Republic); it was done in part while the author was visiting the Simons Institute
for the Theory of Computing
†
Indiana State University, IN, USA arash.rafiey@indstate.edu and Simon Fraser University, BC, Canada,
arashr@sfu.ca, Supported by an NSERC (Canada) grant and a COMPETE (US) grant

1

Specifically, a reflexive digraph H is an adjusted interval digraph if there are two families of real
intervals Iv , Jv , v ∈ V (H), and with the same left endpoint, such that uv ∈ A(H) if and only if
Iu ∩ Jv 6= ∅. Adjusted interval digraphs have efficient recognition algorithms, forbidden structure
characterizations, and certain desirable algorithmic properties [12]. This suggested they should be
the analogue of interval graphs amongst reflexive digraphs. The question of which general digraphs
should be viewed as an appropriate extension of interval graphs remained open.
There is, however, a natural concept for what interval digraphs should be. To motivate this
concept, we introduce the notion of a polymorphism. Given digraphs G and H, a homomorphism
of G to H is a mapping f : V (G) → V (H) such that uv ∈ A(G) implies f (u)f (v) ∈ A(H). A
product of digraphs G and H has the vertex set V (G) × V (H) and arc set E(G × H) consisting of all
pairs (u, x)(v, y) such that uv ∈ A(G) and xy ∈ A(H). The product of k copies of the same graph
H is denoted by H k . A polymorphism of H of order k is a homomorphism of H k to H. In other
words, it is a mapping f from the set of k-tuples over V (H) to V (H) such that if xi yi ∈ A(H) for
i = 1, 2, . . . , k, then f (x1 , x2 , . . . , xk )f (y1 , y2 , . . . , yk ) ∈ A(H). Polymorphisms of H play a pivotal
role in recognizing digraphs (and more general relational systems) G that admit a homomorphism
to H [3] , cf. also [20].
A polymorphism f is conservative if each value f (x1 , x2 , . . . , xk ) is one of the arguments x1 , x2 , . . .
, xk . A binary (order two) f polymorphism that is conservative and commutative (f (x, y) = f (y, x)
for all vertices x, y) is called a CC polymorphism. If f is additionally associative (f (f (x, y), z) =
f (x, f (y, z)) for all vertices x, y, z) it will be called a conservative semi-lattice or an CSL polymorphism. A CSL polymorphism of H naturally defines a binary relation x ≤ y on the vertices of H
by x ≤ y if and only if f (x, y) = x; by associativity, the relation ≤ is a linear order on V (H), which
we call a min ordering of H. In other words, an ordering of vertices v1 < v2 < · · · < vn of H is a
min ordering if and only if uv ∈ A(H), u0 v 0 ∈ A(H) =⇒ min(u, u0 ) min(v, v 0 ) ∈ A(H). Yet another
way to state this is as follows. The ordering v1 < v2 < · · · < vn of V (H) is a min ordering if and
only if uv ∈ A(H), u0 v 0 ∈ A(H) and u < u0 , v 0 < v implies that uv 0 ∈ A(H). It is also clear that,
conversely, a min ordering < of H defines a CSL polymorphism f : H 2 → H by f (x, y) = min(x, y).
Interval graphs are known to have an ordering characterization: H is an interval graph if and
only if V (H) can be linearly ordered v1 < v2 < · · · < vn so that u < v < w and uw ∈ A(H) imply
that uv ∈ A(H). However, it is easy to check, see [24], that a reflexive graph H (every vertex has a
loop) is an interval graph if and only if it has a min ordering. (Note that it is reasonable to define
an interval graph to be reflexive, since any interval intersects itself.) It is also known that a reflexive
digraph is an adjusted interval digraph if and only if it has a min ordering [12]. Moreover, min
ordering on bigraphs (bipartite graphs, or more precisely bipartite digraphs with all edges between
the parts oriented in the same direction) characterizes the class complements of circular arc graphs
[23], and equivalently the class of two-dimensional ray graphs, a natural generalization of interval
graphs in the class of bipartite graphs [19, 32]. Thus, it has long been believed that digraphs
with min ordering are the right notion for the general version of interval digraphs. However, it
was not known whether this class of digraphs can be recognized in polynomial time, whether it
has an obstruction characterization, and whether it has any geometric meaning. We remedy the
situation on all three fronts. We give a geometric representation of the class of digraphs with a min
ordering, we give an obstruction characterization of it, and we also give a certifying polynomial
time recognition algorithm for the class. The existence of such an algorithm was posed as an open
problem in [1, 26]; it is somewhat unexpected, since for more general relational structures the

2

recognition problem is known to be NP-complete [5]. We note that for structures with two binary
relations (digraphs with two kinds of arcs), the recognition problem of having a min ordering is
NP-complete, via a reduction (from a preliminary version of [1]) similar to that in the proof of
Theorem 4.9 [26].
Other questions about the existence of polymorphisms of various kinds have turned out to also
be interesting [2, 5, 13, 22, 25, 31]. In particular, the existence of conservative polymorphisms is
a hereditary property (if H has a particular kind of conservative polymorphism, then so does any
induced subgraph of H). Thus these questions present interesting problems in graph theory. In
particular, we note that there are forbidden induced substructure characterizations for the existence
of conservative majority [25] and conservative Maltsev [7, 25] polymorphisms.
A polymorphism f of H of order k is totally symmetric if f (x1 , x2 , . . . , xk ) = f (y1 , y2 , . . . , yk )
whenever the sets {y1 , y2 , . . . , yk } and {x1 , x2 , . . . , xk } are the same. A set polymorphism of H is
a mapping f of the non-empty subsets of V (H) to V (H), such that f (S)f (T ) ∈ A(H) whenever
S, T are non-empty subsets of V (H) with the property that for each s ∈ S there is a t ∈ T with
st ∈ A(H) and also for every t ∈ T there is an s ∈ S with st ∈ A(H). It is easy to see, cf. [5, 14],
that H has a conservative set polymorphism if and only if it has conservative totally symmetric
polymorphisms of all orders k. In such a case we say H has a CTS polymorphism.
We note that a digraph H that admits a CSL polymorphism also admits a CTS polymorphism:
the conservative set function that assigns to each set S the minimum under the min ordering.
Moreover, a CTS polymorphism applies to all orders, including order two, whence it implies a
CC polymorphism. Thus the class of digraphs with a min ordering is included in the class of
digraphs with a conservative set polymorphism, which is included in the class of digraphs with a
CC polymorphism. We will give forbidden induced structure characterizations for all three of these
digraph classes, from which it will follow that (surprisingly) the first two classes coincide. In all
three cases, the characterizations yield polynomial time recognition algorithms. Although this was
known for CC polymorphisms [14] (even known to be in non-deterministic logspace [5]), it was
open for CSL and CTS polymorphisms [1, 5, 26]. We emphasize that our results are specific to
digraphs; for more general relational structures it is known, for instance, that the existence of CSL
polymorphisms is NP-complete, even with two binary relations [1, 5].

2 Preliminaries
A digraph H consists of a vertex set V (H) and an arc set A(H). Each arc is an ordered pair of
vertices. We say that uv ∈ A(H) is an arc from u to v. Sometimes we emphasize this by saying
that uv is a forward arc of H, and also say vu is a backward arc of H. We say that u, v are adjacent
in H if uv is a forward or a backward arc of H. A walk in H is a sequence P = x0 , x1 , . . . , xn of
consecutively adjacent vertices of H; note that a walk has a designated first and last vertex. A
path P = x0 , x1 , . . . , xn is a walk in which all xi are distinct. A walk P = x0 , x1 , . . . , xn is closed
if x0 = xn and a cycle if all other xi are distinct. A walk is directed if all its arcs are forward. A
vertex u0 is said to be reachable from a vertex u in H if there is a directed walk from u to u0 in H;
a set U 0 is reachable from a set U if some vertex of U 0 is reachable from some vertex of U . Note
that every vertex is reachable from itself, by a directed path of length zero.
For walks P from a to b, and Q from b to c, we denote by P + Q the walk from a to c which is
the concatenation of P and Q, and by P −1 the walk P traversed in the opposite direction, from b

3

to a. We call P −1 the reverse of P . For a closed walk C, we denote by C a the concatenation of C
with itself a times.
The net length of a walk is the number of forward arcs minus the number of backward arcs.
A closed walk is balanced if it has net length zero; otherwise it is unbalanced. Note that in an
unbalanced closed walk we may always choose a direction in which the net length is positive (or
negative). A digraph is unbalanced if it contains an unbalanced closed walk (or equivalently an
unbalanced cycle); otherwise it is balanced. It is easy to see that a digraph is balanced if and only
if it admits a labeling of vertices by non-negative integers so that each arc goes from a vertex with
a label i to a vertex with a label i + 1. The height of H is the maximum net length of a walk in H.
Note that an unbalanced digraph has infinite height, and the height of a balanced digraph is the
greatest label in a non-negative labeling in which some vertex has label zero.
For a walk P = x0 , x1 , . . . , xn and any i ≤ j, we denote by P [xi , xj ] the walk xi , xi+1 , . . . , xj ,
and call it a prefix of P if i = 0. Suppose P = x0 , x1 , . . . , xn is a walk in H of net length k ≥ 0.
We say that H is constricted from below if the net length of any prefix P [x0 , xj ] is non-negative,
and is constricted from above if the net length of any prefix is at most k. We also say that P is
constricted if it is constricted both from below and from above. Moreover, we say that P is strongly
constricted from below or above, if the corresponding net lengths are strictly positive or smaller
than k. For walks P of net length k < 0, we say that P is (strongly or not) constricted below, or
above, or both, if the above definitions apply to the reverse walk P −1 .
Consider a cycle C in H of non-zero net length k. A vertex v is extremal in C if either k > 0 and
traversing C, starting at v in the positive direction yields a walk constricted from below, or k < 0
and traversing C (starting at v) in the negative direction yields a walk constricted from above. We
observe that a cycle C of positive net length k has k extremal vertices, since starting at any vertex
x the net length of the prefix C[x, v] varies from 0 to a possibly negative minimum m, but ending
with k > 0. We can let v0 be the last vertex with the net length of C[x, v0 ] equal to the minimum
m (possibly v0 = x if m = 0). We can let vi be the last vertex with the net length of C[v0 , vi ]
equal to i, i = 1, 2, . . . , k − 1. Note that each walk C[vi , vi+1 ] is constricted from below and has net
length one. We also note for future reference that any other extremal vertex of C has a walk of net
length zero to one of v0 , v1 , . . . , vk−1 . Similar observations apply when C has a negative net length.
A cycle of H is induced if H contains no other arcs on the vertices of the cycle. In particular, an
induced cycle with more than one vertex does not contain a loop.
The following lemma is well known. (For a proof, see [21, 37] or Lemma 2.36 in [24]).
Lemma 2.1 Let P1 and P2 be two constricted walks of net length r. There exists a constricted
path P of net length r that admits a homomorphism f1 to P1 and a homomorphism f2 to P2 , such
that each fi , i = 1, 2 takes the starting vertex of P to the starting vertex of Pi and the ending vertex
of P to the ending vertex of Pi .
We call P a common pre-image of P1 and P2 . In particular, we emphasize that we use the term
pre-image of a path P 0 to be a path P that admits a homomorphism to P 0 taking the first vertex
of P to the first vertex of P 0 and the last vertex of P to the last vertex of P 0 .
We visualize P as following the arcs of P1 (respectively P2 ), starting where P1 (respectively P2 )
starts and ending where P1 (respectively P2 ) ends, but possibly taking intermediate back and forth
steps. When we mention pre-images of walks, we shall always assume that the pre-image starts at
the starting vertex and ends at the ending vertex of the original walk.

4

3 Warm-up: Obstructions to CC polymorphisms
In this section we introduce a construction that will be used throughout the paper. We also
illustrate the techniques on the easy case of CC polymorphisms. As mentioned earlier, the existence
of CC polymorphisms is well understood; it is solvable by 2-SAT [14, 15], so it is both known to
be decidable in polynomial time and characterized by forbidden substructures [33]. In fact, it is
shown in [5] that it can be decided in non-determinstic logspace. Nevertheless, we present our
obstructions to the existence of CC polymorphism because they illuminate the general obstructions
to CSL polymorphisms, and underscore the relationship between the two types of polymorphisms
and their obstructions.
Suppose f is a CC polymorphism of H. If xx0 , yy 0 ∈ A(H) but xy 0 6∈ A(H), then f (x, y) = x
implies f (x0 , y 0 ) = x0 . A similar situation arises if x0 x, y 0 y ∈ A(H) but y 0 x 6∈ A(H): again f (x, y) =
x implies f (x0 , y 0 ) = x0 .
We define two walks P = x0 , x1 , . . . , xn and Q = y0 , y1 , . . . , yn in H to be congruent, if they
follow the same pattern of forward and backward arcs, i.e., xi xi+1 is a forward (backward) arc if
and only if yi yi+1 is a forward (backward) arc (respectively). Suppose the walks P, Q as above are
congruent. We say an arc xi yi+1 is a faithful arc from P to Q, if it is a forward (backward) arc when
xi xi+1 is a forward (backward) arc (respectively), and we say an arc yi xi+1 is a faithful arc from
Q to P , if it is a forward (backward) arc when xi xi+1 is a forward (backward) arc (respectively).
We say that P avoids Q if there is no faithful arc from P to Q at all.
We note for future reference that if two congruent walks P, Q avoid each other, then the same is
true for any common pre-images P 0 , Q0 . (Note that if P avoids Q, it is not necessarily true that P 0
avoids Q0 because of the back steps involved in the pre-images.)
We define the pair digraph H + as follows. The pairs of H + are all ordered pairs (x, y) of distinct
vertices of H, and (x, y)(x0 , y 0 ) ∈ A(H + ) just if
• xx0 , yy 0 ∈ A(H) but xy 0 6∈ A(H), or
• x0 x, y 0 y ∈ A(H) but y 0 x 6∈ A(H).
In the former case we call the arc (x, y)(x0 , y 0 ) ∈ A(H + ) a positive arc, and the the second case
we call it a negative arc. We say positive arc (x, y)(x0 , y 0 ) is symmetric if xx0 , yy 0 ∈ A(H) but
xy 0 , yx0 6∈ A(H) We say negative arc (x, y)(x0 , y 0 ) is symmetric if x0 x, y 0 y ∈ A(H) but y 0 x, x0 y 6∈
A(H). A path in H + is symmetric if all its arcs are symmetric.
Note that in H + we have an arc from (x, y) to (x0 , y 0 ) if and only if there is an arc from (y, x) to
0
(y , x0 ). We call this the skew property of H + .
Note that a directed walk W in H + corresponds precisely to a pair of congruent walks P, Q in
H such that P avoids Q. The net value of the directed walk W is defined to be the net length of
the walk P (or Q). It is the difference between the number of positive and negative arcs of W . We
say that W has constricted values if the walk P (or Q) is constricted, i.e., if each initial segment
of W has net value between zero and the net value of W . Walks with values constricted below or
above are defined similarly.
According to our observation, having a directed walk in H + from (x, y) to (x0 , y 0 ) means that
f (x, y) = x implies that f (x0 , y 0 ) = x0 in any CC polymorphism f of H. In particular, for any
strong component C of H + , and any CC polymorphism f of H, either all pairs (x, y) ∈ C are

5

mapped by f to the first coordinate or all are mapped to the second coordinate. Moreover, if C2 is
reachable from C1 in H + , and f maps pairs in C1 to the first coordinate, then it also maps pairs
in C2 to the first coordinate. An invertible pair of H is a vertex (x, y) of H + such that (x, y) and
(y, x) are in the same strong component of H + . It is easy to see, using the skew property of H + ,
that if one vertex of a strong component of H + is invertible, then so are all others, and, that if H
has no invertible pairs, then each component C has a corresponding dual component C 0 such that
(x, y) ∈ C if and only if (y, x) ∈ C 0 . In fact, constructing a CC polymorphism for H amounts to
selecting, one strong component from each pair C, C 0 of dual strong components, to map f to the
first coordinate, in such a way, that if C2 is reachable from C1 in H + , and C1 was selected, then
C2 is also selected. This is easy to do, for instance by the following algorithm.
We say that a strong component C of a digraph is ripe if no other strong component is reachable
from it. The algorithm begins by selecting a ripe strong component C of H + , and deleting it and
its dual C 0 from H + , continuing the same way with the remaining digraph.
This algorithm clearly selects exactly one pair from (x, y), (y, x) for each x 6= y. It remains to
prove that if (x, y) is selected and (x, y)(x0 , y 0 ) is an arc of H + , then (x0 , y 0 ) is also selected. This
is clear if (x, y), (x0 , y 0 ) are from the same strong component of H + . Otherwise, suppose for a
contradiction, that (x, y) was selected in a component C after (x0 , y 0 ) was deleted in a component
D0 , where D was selected (before C). By the skew property of H + , we see that D has an arc to
C 0 , so it was selected when it was not yet ripe.
Theorem 3.1 A digraph H admits a CC polymorphism if and only if no strong component of H +
contains an invertible pair.


4 Min Ordering and Geometric Representation
In this section we introduce a geometric representation of digraphs that admit a min-ordering. Let
C be a circle with two distinguished points (the poles) N and S, and let H be a digraph. Let
Iv , v ∈ V (H) and Jv , v ∈ V (H) be two families of arcs on C such that each Iv contains N but not
S, and each Jv contains S but not N . We say that the families Iv and Jv are consistent if they
have the same clockwise order of their clockwise ends, i.e., if the clockwise end of Iv precedes in
the clockwise order the clockwise end of Iw if and only if the clockwise end of Jv precedes in the
clockwise order the clockwise end of Jw . Suppose two families Iv , Jv are consistent; we define an
ordering < on V (H) where v < w if and only if the clockwise end of Iv precedes in the clockwise
order the clockwise end of Iw ; we call < the ordering generated by the consistent families Iv , Jv .
A bi-arc representation of a digraph H is a consistent pair of families of circular arcs, Iv , Jv , v ∈
V (H), such that uv ∈ A(H) if and only if Iu and Jv are disjoint. A digraph H is called a bi-arc
digraph if it has a bi-arc representation.
Theorem 4.1 A digraph H admits a min ordering if and only if H is a bi-arc digraph.
Proof: Suppose Iv , Jv form a bi-arc representation of H. We claim that the ordering < generated
by Iv , Jv is a min ordering of H. Indeed, suppose u < u0 and v 0 < v have uv, u0 v 0 ∈ A(H). Then Iu0
spans the area of the circle between N and the clockwise end of Iu , and Jv spans the area of the circle
between S and the clockwise end of Jv0 . (See Figure 1.) This implies that Iu and Jv0 are disjoint:

6

N
...
...

Iu’

Jv

Iu

Jv’
...
...

S

Figure 1: Illustration for the proof of Lemma 4.1

indeed, the counterclockwise end of Iu is blocked from reaching Jv0 by Jv (since uv ∈ A(H)),
and the counterclockwise end of Jv0 is blocked from reaching Iu by Iu0 (sinceu0 v 0 ∈ A(H)). (The
clockwise ends are fixed by the ordering <.)
Conversely, suppose < is a min ordering of H. We construct families of arcs Iv and Jv , with
v ∈ V (H), as follows. The intervals will Iv contain N but not S, the intervals Jv will contain S but
not N . The clockwise ends of Iv are arranged in clockwise order according to <, as are the clockwise
ends of Jv . The counterclockwise ends will now be organized so that Iv , Jv , v ∈ V (H) becomes a
bi-arc representation of H. For each vertex v ∈ V (H), let ov denote the last out-neighbour of v, and
let iv denote the last in-neighbour of v, where ”last” refers to the order <. Then we extend each Iv
counterclockwise as far as possible without intersecting Jov , and extend each Jv counterclockwise
as far as possible without intersecting Iiv . We claim this is a bi-arc representation of H. Clearly, if
w > ov , then Iv intersects Jw by the construction, and similarly for u > iv we have Jv intersecting
Iu . This leaves disjoint all pairs Iu , Jv such that u ≤ iv and v ≤ ou ; since uou , iv v are arcs of H,
the definition of min ordering implies that uv is in fact an arc of H, as required.

If < is a min ordering of H, then min (with respect to <) is a CC polymorphism of H, so much of
the above observations apply verbatim. If xx0 , yy 0 ∈ A(H) but xy 0 6∈ A(H), (or if x0 x, y 0 y ∈ A(H)
but y 0 x 6∈ A(H)), then x < y implies x0 < y 0 . (Note that otherwise x < y, y 0 < x0 would violate the
min property).
A circuit in H + is a set of pairs (x0 , x1 ), (x1 , x2 ), . . . , (xn−1 , xn ), (xn , x0 ) of H + . Note that an
invertible pair of H is a circuit with n = 1 in a strong component of H + .
If a strong component of H + contains a circuit, then H cannot have a min ordering, since x0 < x1
implies x0 < x1 < x2 < · · · < xn < x0 (and similarly for x0 > x1 ), contradicting the transitivity of
<. We have proved one direction of the following result.
Theorem 4.2 A digraph H admits a min ordering if and only if no strong component of H +
contains a circuit.
This nicely complements Theorem 3.1, highlighting the difference in the obstructions.
We now single out a particular situation in which a circuit occurs in one strong component of
the pair digraph H + .
Theorem 4.3 If H contains an induced cycle of net length greater than one, then a strong component of H + contains a circuit.

7

Proof: Suppose C is an induced cycle of net length k > 1. Recall that the cycle C has k extremal
vertices v0 , v1 , . . . , vk−1 with each C[vi , vi+1 ] (subscript addition modulo k) constricted from below
and of net length one.
We shall show that (v0 , v1 ), (v1 , v2 ), . . . , (vk−1 , v0 ) belong to the same strong component of H + .
Indeed, for any i = 1, . . . , k − 1, we shall exhibit a directed walk in H + from (xi−1 , xi ) to (xi , xi+1 ).
These directed walks in H + will be constructed out of pairs of walks on the cycle C.
Assume first that the height of C[vi−1 , vi ] is at most the height of C[vi , vi+1 ]. To be able to use
Lemma 2.1, we consider the last vertex h of C[vi , vi+1 ] maximizing the net length of C[vi , h], and
the first vertex h0 of C[vi , vi+1 ] such that C[h0 , h] has net length one.
Now C[vi−1 , h0 ] and C[vi , h] are constricted and have the same net length. Thus by Lemma 2.1
they have a common pre-image A. Also C −1 [h0 , vi ] and C[h, vi+1 ] are constricted and have the
same net length; thus they also have a common pre-image B. Let X be the walk in C from vi−1
to vi corresponding to A + B, and let Y be the walk in C from vi to vi+1 corresponding to A + B.
We claim that X avoids Y . Consider the j-th vertex u of X, and the (j + 1)-st vertex v of Y .
Note that the net lengths of C[v0 , u] and C[v0 , v] differ by two; since C is an induced cycle of net
length greater than one, there can be no faithful arc between u and v. This implies that there is a
directed path in H + from (vi−1 , vi ) to (vi , vi+1 ).
If the height of C[vi−1 , vi ] is greater than the height of C[vi , vi+1 ], we argue analogously. We
denote by P the infinite walk obtained by continuously following C in the positive direction. Let
h be the last vertex of C[vi−1 , vi ] maximizing the net length of C[vi−1 , h], and let h0 be the first
vertex of P after vi+1 such that P [h, h0 ] has net length zero. Now Lemma 2.1 can be applied to
the walks C[vi−1 , h] and C[vi+1 , h0 ], and to the walks C[h, vi ] and P −1 [h0 , vi+1 ], yielding a common
pre-image A for the former pair and a common pre-image B for the latter pair. The walk X in C
from vi−1 to vi corresponding to A + B again avoids the walk Y in P from vi to vi+1 corresponding
to A + B.

We note that the avoidance of the walks didn’t quite need that the cycle C be induced. It should
just not have certain chords. We state a useful version as follows.
Corollary 4.4 Suppose C is a closed walk in H of net length greater than one, and x, y are two
extremal vertices of C such that the net length of C[x, y] is positive. Let Px be the infinite walk
starting at x, obtained by continuously following the cycle C in the positive direction and let Py be
obtained the same way starting at y. Let X, Y be two congruent walks such that X avoids Y and X
and X is a common pre-image of Px , Py and Y is also a common pre-image of Px , Py . Then some
strong component of H + contains a circuit.

5 The Algorithm
We are now ready to claim the converse of Theorem 4.2.
Theorem 5.1 A digraph H admits a min ordering if and only if no strong component of the pair
digraph H + contains a circuit.
To prove the converse, we introduce an algorithm to construct a min ordering < of H, provided
no strong component of the pair digraph H + contains a circuit. This will prove Theorem 5.1.

8

Thus we shall assume that no strong component of H + contains a circuit.
At each stage of the algorithm, there are some pairs of H + that have been chosen, and others
that have been discarded. Let Vc denote the set of chosen pairs, and Vd the set of discarded pairs;
the pairs in the set S = V (H + ) \ (Vc ∪ Vd ) are called the remaining pairs. Initially we will have
Vc = Vd = ∅, and throughout the algorithm we will maintain the following properties:
• (a, b) ∈ Vc if and only if (b, a) ∈ Vd ;
• if (a, b) ∈ Vc and (a, b)(a0 , b0 ) ∈ A(H + ) then (a0 , b0 ) ∈ Vc ;
Consequently, we will always have Vc ∩ Vd = ∅, and each strong component of H + lies entirely
in one of the three sets Vc , Vd , S.
Moreover, at the end of the algorithm the set S will be empty and we will have the following
additional property:
• if (a, b) ∈ Vc and (b, c) ∈ Vc then (a, c) ∈ Vc
A step of the algorithm will consist of selecting one vertex (a, b) ∈ S to be chosen (moving (a, b)
to Vc ), and choosing all pairs (a0 , b0 ) ∈ S that can be reached from (a, b) in H + . (It is easy to check
that a vertex that can be reached from (a, b) ∈ S in H + cannot be in Vd : otherwise (b, a) ∈ Vc
can reach (b0 , a0 ), thus (b0 , a0 ) ∈ Vc , contradicting (a0 , b0 ) ∈ S.) So we use the term selected vertex
for this special vertex, and the term selected strong component for the strong component of H +
containing the selected vertex.
Recall that a strong component of H + is balanced if every closed directed walk has net value
zero, i.e., the same number of positive and negative arcs. A pair of H + is called balanced if it lies
in a balanced strong component.
Let H ∗ be the sub-digraph of H + induced by balanced pairs. The pairs in H ∗ can be assigned
levels so that if (a, b)(c, d) is a positive arc in H + , then the level of (c, d) is one more than the level
of (a, b), and if (a, b)(c, d) is a negative arc in H + , then the level of (c, d) is one less than the level
of (a, b).
Recall that a strong component of H + is balanced if every closed directed walk has net value zero,
i.e., the same number of positive and negative arcs. Let H ∗ be the set of balanced components in
H +.
A pair (x, y) in H + is called extremal if the following hold.
• (x, y) lies on a direct cycle D = (X, Y ) in H +
• X, Y are closed walks in H such that X avoids Y .
• x, y are extremal vertices on X, Y respectively.
A vertex a ∈ V (H) is a source for a set S, S ⊆ V (H + ), if for every vertex b ∈ V (H) we have the
following property:
• no (c, a) ∈ S is reachable from any (a, b) ∈ S in H +

9

Algorithm 1 Algorithm to find a min ordering of input digraph H
1: function MinOrdering(H)
2:
Construct H + and compute its (strong) components
3:
if a component of H + contains a circuit then return False
4:
if H + has an unbalanced component then
5:
Set S = the set of all extremal pairs
. extremal pairs are in unbalanced components
6:
Set Vc = Vd = ∅
7:
while S 6= ∅ do
8:
Find a source p for S
9:
while there is a pair (p, q) ∈ S do
10:
move all pairs from S reachable from (p, q) to Vc
11:
move all pairs from S that can reach (q, p) to Vd
12:
Construct H ∗ , set R = V (H ∗ ), and compute the levels of all pairs
13:
while R 6= ∅ do
14:
Set S = the set of all pairs at the lowest level ` of R, and remove them from R
15:
while S 6= ∅ do
16:
Find a vertex p ∈ V (H) that respects transitivity in V (H ∗ ) ∩ Vc
17:
while there is a pair (p, q) ∈ S do
18:
move all pairs from S reachable from (p, q) to Vc
19:
move all pairs from S that can reach (q, p) to Vd
Let B ⊆ V (H + ). We say S has a source p that respects transitivity in B if for no (p, q) ∈ S there
is a chain of pairs (q, p1 ), (p1 , p2 ), . . . , (pr−1 , pr ), (pr , p) all in B.
Note that the moves in lines 10,11,18,19 mean remove the moved vertices from the set S.
We will show that a source exists for any of the sets S encountered by the algorithm. Proposition
9.4 shows this for the first phase of the algorithm, handling unbalanced strong components (lines 411). It also shows that that throughout this phase the set Vc does not contain a circuit. Proposition
10.1 similarly handles the second phase (lines 12-19), handling the remaining balanced components
of H + . In other words, the set Vc does not contain a circuit throughout the execution of the
algorithm.
At the end of the algorithm we exactly one pair from each (x, y), (y, x) is chosen (present in Vc ).
Recall that the choices ensure that if (x, y) ∈ Vc and it has an arc to (x0 , y 0 ) in H + , then (x0 , y 0 ) ∈ Vc
as well. We define a binary relation < by setting x < y if (x, y) ∈ Vc . Since there is no circuit
among the chosen pairs, the relation < is transitive, and hence a total order. Moreover, < is a min
ordering. Indeed, suppose x < x0 , y 0 < y and xy, x0 y 0 ∈ A(H) but xy 0 6∈ A(H). Note that (x, x0 )
has an arc to (y, y 0 ) in H + ; thus since x < x0 , the pair (x, x0 ) ∈ Vc , and so (y, y 0 ) should have been
in Vc as well, contrary to y 0 < y.
In what follows we assume that there is no circuit in a strong component of H + .

10

6 Structural properties of the walks in H
For simplicity, for two pairs (u, v), (u0 , v 0 ) let (u, v)
(u0 , v 0 ) denote that (u0 , v 0 ) is reachable from
(u, v) in H + and also denote a direct path in H + from (u, v) to (u0 , v 0 ). If there is not direct path
in H + from (u, v) to (u0 , v 0 ) then we write (u, v) 6 (u0 , v 0 ).
In this section we formulate some useful facts. The first two deal with a situation where four
walks A, B, C, D start in four distinct vertices, but the end vertices of walks B and C coincide.
Note that this means that B does not avoid C, and vice versa. (At the last step, there is a faithful
arc.) The statements serve to identify situations in which all the other pairs avoid each other, i.e.,
A avoids B, C, D; B avoids A, D; C avoids A, D; and D avoids A, B, C. In the first lemma, we start
with congruent walks A, B, C, D, while in the second lemma only A, B are congruent, and C, D are
congruent; but on the other hand, all four walks are constricted and have the same height, so we
can replace them by their common pre-images by Lemma 2.1.
Lemma 6.1 Let A, B, C, D be four congruent walks in H, from p, q, r, s to a, b, b, d respectively,
such that A avoids B and C avoids D.
Suppose in H +
• (p, q) 6

(a, d) and (p, q) 6

(d, b),

• (r, s) 6

(a, d) and (r, s) 6

(b, a)

Then all pairs from A, B, C, D avoid each other, except the pair B, C.
Proof: Let A be the walk p = a1 , a2 , . . . , an = a, B the walk q = b1 , b2 , . . . , bn = b, C the walk
r = c1 , c2 , . . . , cn = b, and D the walk s = d1 , d2 , . . . , dn = d.
Let Si denote the statement that all pairs from A[ai+1 , a], B[bi+1 , b], C[ci+1 , b], D[di+1 , d] avoid
each other, except possibly B[bi+1 , b], C[ci+1 , b]. The Lemma claims that S0 holds, while Sn−1 holds
vacuously. Therefore, let i, 0 ≤ i ≤ n − 1 be the first index such that Si holds.
Note that ai di+1 is not a faithful arc. Otherwise, (p, q)
(d, b) in H + by combining two walks
in H, namely the walk A[p, ai ] concatenated with D[di+1 , d], and the walk B. This implies that
bi di+1 is also not a faithful arc, since otherwise (p, q)
(a, d) by combining the walks A and B[q, bi ]
concatenated with D[di+1 , d]. (This uses the fact that ai di+1 is not a faithful arc.)
By a similar line of reasoning, we conclude that
• ci ai+1 is not a faithful arc (as otherwise (r, s)
(otherwise (r, s)
(b, a)).

(a, d)), and then di ai+1 is not a faithful arc

• di bi+1 is not a faithful arc (as otherwise (p, q)
otherwise (r, s)
(a, d)).

(a, c)), and bi ai+1 is not a faithful arc (as

Together with the fact that ai bi+1 and ci di+1 are not faithful arcs (corresponding to the assumption that A avoids B and C avoids D), we obtain a contradiction with the minimality of i; therefore
i = 0, and the lemma is proved.

A similar result applies to walks that are not all congruent, as long as they are constricted and
have the same net length. (Of course the pairs of walks that one avoids another one must be
congruent by definition.)

11

Corollary 6.2 Let A, B, C, D be four constricted walks of the same net length, from p, q, r, s to
a, b, b, d respectively, such that A, B are congruent and A avoids B, and C, D are congruent and C
avoids D.
Suppose in H +
• (p, q) 6

(a, d) and (p, q) 6

(d, b),

• (r, s) 6

(a, d) and (r, s) 6

(b, a)

Then there exist congruent walks A0 , B 0 , C 0 , D0 that are pre-images of A, B, C, D respectively, such
that all pairs from A0 , B 0 , C 0 , D0 avoid each other, except the pair B 0 , C 0 and hence A, B avoid each
other and C, D avoid each other.
Proof: Let A be the walk p = a1 , a2 , . . . , an = a, B the walk q = b1 , b2 , . . . , bn = b, C the walk
r = c1 , c2 , . . . , cm = b, and D the walk s = d1 , d2 , . . . , dm = d. We prove the Corollary by induction
on the sum of the lengths m + n. If m + n = 0, i.e., m = n = 0, this holds trivially.
Suppose first that A, B, C, D are strongly constricted from below. This means that the first two
arcs in each walk are forward arcs, and the walks A − p, B − q, C − r, D − s are also constricted
walks of the same net length, with the first two congruent and the last two congruent. Moreover, in
H + , neither (a, d) nor (d, b) is reachable from (a2 , b2 ), otherwise they would also be reachable from
(p, q) because A is assumed to avoid B. Similarly, neither (a, d) nor (d, b) is reachable from (c2 , d2 ).
By the induction hypothesis, A − p, B − q, C − r, D − s have congruent pre-images A00 , B 00 , C 00 , D00
in which all pairs except B 00 , C 00 avoid each other. Noting that A00 starts in a2 , we let A0 consist of
p concatenated with A00 (i.e., A0 = a1 a2 + A00 ), let B 0 be q concatenated with B 00 , and similarly for
C 0 and D0 . Since A0 , B 0 , C 0 , D0 are all congruent, we can apply Lemma 6.1, and conclude that all
pairs avoid each other, except the pair B 0 , C 0 .
In the rest of the proof we will show that B also avoids A, and that D also avoids C; in other
words, that A, B avoid each other and that C, D avoid each other. By repeated application of
Lemma 2.1 we conclude that there exist congruent walks A0 , B 0 , C 0 , D0 from p, q, r, s to a, b, b, d
that are pre-images of A, B, C, D respectively. Since A and B are congruent and avoid each other,
the walks A0 , B 0 follow the same sequence of back and forth steps inside A, B, and also avoid each
other. (Note that if A0 , B 0 take a backward step along A, B we can only conclude A0 avoids B 0 if we
know that also B avoids A.) Similarly, C 0 , D0 also avoid each other. Therefore we can now apply
Lemma 6.1 to A0 , B 0 , C 0 , D0 and conclude that all pairs from A0 , B 0 , C 0 , D0 avoid each other, except
the pair B 0 , C 0 .
Since we have already considered the case when all four walks A, B, C, D are strongly constricted
from below, we may assume, up to symmetry, that A, B are not strongly constricted from below, i.e.,
that there exists a subscript j > 1 such that A[p, aj ] and B[q, bj ] have net length zero. We take the
subscript j is as large as possible, therefore A[aj , a], B[bj , b] are strongly constricted from below and
have the same net length as C, D. We now apply the induction hypothesis to A[aj , a], B[bj , b], C, D
and conclude that A[aj , a], B[bj , b], C, D have congruent pre-images that pairwise avoid each other
(except for the pre-images of B[bj , b], C). This implies that A[aj , a], B[bj , b] also avoid each other,
and C, D also avoid each other. If C, D were also not strongly constricted from below, we could
draw the similar conclusion that A, B avoid each other, as claimed. However, in general C, D
may happen to be strongly constricted from below, and we proceed more carefully as follows:

12

recall that our goal is to prove that A and B avoid each other. Noting that by the definition
of j the arcs aj−1 aj and bj−1 bj are backward arcs; moreover, the first arcs c1 c2 , d1 d2 of C, D are
forward arcs. Since A avoids B and C and D avoid each other, we can apply Lemma 6.1 to
A[aj−1 , a], B[bj−1 , b], c2 c1 + C, d2 d1 + D and conclude that A[aj−1 , a], B[bj−1 , b] have pre-images
that avoid each other, and hence that A[aj−1 , a], B[bj−1 , b] also avoid each other. The idea of the
proof is to continue this way backwards on A, B until proving that they avoid each other in their
entirety.
Thus let i ≤ j be the minimum subscript such that A[ai , a], B[bi , b] avoid each other and there
exists an ` such that A[ai , aj ] has a common pre-image with a walk WC in C that starts in some
vertex c` and ends in c1 ; then A[ai , a] has a common pre-image with WC + C. (Of course, this is
also a pre-image of B[bi , b] and W 0 + D where WD is congruent to WC and starts in d` and ends in
d1 .) We have just shown that i ≤ j − 1 and for i = j − 1 we can take ` = 2. We claim that i = 1,
which means in particular that A, B avoid each other. We proceed by contradiction.
Let X, Y, Z, U be congruent walks that are pre-images of A[ai , a], B[bi , b], WC + C, WD + D respectively, and denote by xt , yt , zt , ut the t-th vertices of these walks respectively.
Suppose first that ai−1 ai is a forward arc. We would like to show that A[ai−1 , a], B[bi−1 , b] avoid
each other and have a common pre-image with WC0 + C that starts in some c`0 . If c`+1 c` is also
a forward arc, we can set `0 = ` + 1 and argue as above, adding ai−1 ai to X and c`+1 c` to Z.
Otherwise, we claim there is another vertex `00 and another walk WC00 in C that starts in c`00 and
ends in c1 and has a common pre-image with A[ai , aj ], and such that c`+1 c` is a forward arc (so
we can proceed as above). Note that we have x1 = ai ; we let t be the last subscript such that
X[x1 , xt ] is constricted from below and has net length zero. Then it is easy to see that xt xt+1 is
a backward arc. Indeed, the net length of A[ai , aj ] is strictly negative, as ai−1 ai is a forward arc,
A is constricted, and A[a1 , aj ] has net length zero. Since X and Z are congruent, zt zt+1 is also a
backward arc, and we can set c`00 = zt . It remains to construct a walk WC00 in C, from c`00 to c1 that
has a common pre-image with A[ai , aj ]. Note that the walk X[x1 , xt ] from x1 = ai to xt is congruent
with the walk Z[z1 , zt ] from z1 = c` to zt = c`00 . Both are constricted from below, and have the
same maximum net length of a subwalk; say X[x1 , xs ] and Z[z1 , zs ] are of maximum net length.
Then applying Lemma 2.1 twice (once to X[x1 , xs ], Z −1 [zt , zs ] and once to X −1 [xs , x1 ], Z[zt , zs ], we
obtain congruent walks X ∗ , Z ∗ from ai to ai and from c`00 to c` respectively. Then the concatenation
WC00 = Z ∗ + Z is a walk in C from c`00 to c1 that has a common pre-image X ∗ + X with A[ai , aj ],
as required.
When ai−1 ai is a backward arc, the proof is similar. If c`+1 c` is also a backward arc, we proceed
as usual. Otherwise, we let t be the last subscript such that X[x1 , xt ] is constricted from above
and of net length zero. This again means that xt xt+1 and hence also zt zt+1 is a forward arc, and
we set c`00 = zt . Then choosing xs so that the net length of X[x1 , xs ] is minimized, and applying
Lemma 2.1 twice – to X[x1 , xs ], Z −1 [zt , zs ] and to X −1 [xs , x1 ], Z[zt , zs ], we obtain congruent walks
X ∗ , Z ∗ from ai to ai and from c`00 to c` respectively, which yield the walk Z ∗ + Z in C from c`00 to
c1 that has a common pre-image X ∗ + X with A[ai , aj ], as required.

Here is another useful version of the lemma (cf. Figure ??).
Lemma 6.3 Suppose that n ≥ t > 1, ` > 0 are integers, (a0 , a1 ), (a1 , a2 ), . . . , (an , a0 ) is a circuit
in H + , and, for each i = 0, 1, . . . , t, pi , qi , gi , hi are vertices of H, and Ai , A0i , Bi , Bi0 are walks in
H, such that the following statements hold (subscript addition modulo n + 1):

13

gi

hi

A0i+1
A0i
0
Bi+1

Bi
Bi+1

Ai

Ai+1

Bi0

qi

gi

qi+1

A0i

ai+1

gi+1

hi

Bi0

Bi

pi

ai

hi+1

0
Bi+1

Ai

A0i+1

Bi+1

qi

ai

pi

pi+1

Ai+1

qi+1

ai+1

pi+1

Figure 2: Top Figure : The notation for the walks Ai , Bi , A0i , Bi0 and bottom Figure is an example
for such walks

1. Ai is a constricted walk from pi to hi of net length `
2. Bi is a constricted walk from qi to gi of net length `
3. A0i is a constricted walk from hi to ai of net length −`
4. Bi0 is a constricted walk from gi to ai of net length −`
0
5. Ai + A0i is congruent to and avoids Bi+1 + Bi+1

6. if k 6= j + 1, then (pi , qi+1 ) 6

(aj , ak )

Let C be any one of the walks A0i or Bi0 or A−1
or of Bi−1 , and let D be any one of the walks A0j
i
−1
or Bj0 or A−1
j or of Bj , with i 6= j.
Then C, D have common pre-images that avoid each other.
Note that condition 5 implies that (pi , qi+1 )
that
7 if (ai , ai+1 )

(ai , ai+1 ) in H + , and therefore condition 6 implies

(aj , ak ) in H + , then k = j + 1

Another way to state the conclusion of the lemma is the following.
−1
There are common pre-images of all A0i , Bi0 , A−1
i , Bi , i = 0, 1, . . . , t, such that any two pre-images
of walks with different subscripts avoid each other.
The lemma will often be used for walks where A0i = A−1
and/or Bi0 = Bi−1 (or even A0i = A−1
i
i =
−1
= Bi ).

Bi0

14

Proof: We prove the lemma with t = n, and it is easy to check that the proof allows any smaller
t, t ≥ 2.
We first prove that any Bi0 , Bj0 with i 6= j have common pre-images that avoid each other. We
proceed by induction on |j − i|. If |j − i| = 1, say j = i + 1, we may apply Corollary 6.2 to the walks
0 . Indeed, A0
0
0
0
A0i−1 , Bi0 , A0i , Bi+1
i−1 avoids Bi and Ai avoids Bi+1 by 5, and since the same condition
+
also implies that (pi , qi+1 )
(hi , gi+1 ) in H , condition 6 implies that (hi , gi+1 ) 6 (ai−1 , ai+1 )
and (hi , gi+1 ) 6 (ai , ai−1 ), and similarly for (hi−1 , gi ). (Here we used the fact that n > 1.)
0
For the induction step, we again assume that i < j and consider Bi0 , Bj0 , Bj+1
. By the induction
0
0
hypothesis, there are common pre-images of Bi , Bj that avoid each other and also common pre0
images of Bj0 , Bj+1
that avoid each other. As noted earlier, we may assume that all these pre-images
are congruent to each other. Now assume there is a faithful arc from Bi to Bj+1 , or from Bj+1 to
Bi . It is easy to trace walks from (ai , aj ) on reverses of Bi0 , Bj0 (that are known to avoid each other)
0
up to the faithful arc, use the faithful arc, and then follow the walks Bj+1
, Bj0 , also known to avoid
each other to (aj+1 , aj ). This would imply that (aj , aj+1 )
(aj , ai ) which contradicts condition 7,
and completes the induction proof.
A symmetric argument yields that any A0i , A0j with i 6= j have common pre-images that avoid
each other.
It now follows that any A0i , Bj0 , i 6= j, have common pre-images that avoid each other. Indeed,
0
0
0 , B0
Ai , Bi+1
are congruent by assumption, so it suffices to take the common pre-images of Bi+1
j
that avoid each other, we have just constructed, and also use the same pre-image for A0i . Then if
there was a faithful arc between A0i and Bj0 (in either direction), we could use it to reach (aj , ai )
0 , the faithful arc, and a portion of
from (pi , qi+1 ), using the walks Ai , Bi+1 , A0i , a portion of Bi+1
Bj0 . This contradicts condition 6 of the lemma. (We note that since n > 2, we can always choose
i, j so that j + 1 6= i.)
Next we argue that for each j 6= i there are common pre-images to Ai , Bi+1 , Aj , Bj+1 , such that
each pair except for the pre-images of Bi+1 and Aj avoid each other. This will in particular imply
that the pre-images of Ai and Aj avoid each other, and the pre-images of Ai and Bj+1 avoid each
other. It will also imply that Ai , Bi+1 avoid each other, and thus Ai , Bj avoid each other for all
j 6= i. This will imply the corresponding statements also about their reverses. For any i 6= j,
consider a new digraph H o obtained from H by the addition of three new vertices u, v, w and four
new arcs hi u, gi+1 v, hj v, gj+1 w (see Figure 3). Then in H o we will apply Corollary 6.2 to the walks
Ai + hi u, Bi+1 + gi+1 v, Aj + hj v, Bj+1 + gj+1 w, to conclude that Ai , Aj as well as Ai , Bj+1 have
common pre-images that avoid each other. The assumptions of Corollary 6.2 are easy to check
using the statements we have already proved. For instance, (pi , qi+1 ) 6 (u, w) since otherwise we
0
would have (pi , qi+1 )
(hi , gj+1 ). Since we have already proved that A0i , Bj+1
avoid each other,
this implies that (pi , qi+1 )
(hi , gj+1 ), contradicting assumption 6 of the lemma.
It remains to check the primed walks against the reverses of the unprimed walks. The ar−1
guments are symmetric, we focus on finding common pre-images of A0i , B 0 i + 1, A−1
j , Bj+1 . We
again construct a new digraph H o with added vertices u, v, w and arcs ai u, ai+1 v, pj v, qj+1 w. It is
again easy to check, from the statements already proved, that Corollary 6.2 applies to the walks
−1
−1
0
0
A0i + ai u, Bi+1
+ ai+1 v, A−1
j + aj v, Bj+1 + qj+1 w to imply that Ai and Aj avoid each other, and
−1
−1

that A0i and Bj+1 as well as A0i and Bi+1 also avoid each other.

15

u

w
v

hi

A0i

Bi
Bi0

hj

Bi+1
Ai

ai

hi+1

gi+1

pi

Bj

Bj0

0
Bi+1

qi+1

A0j
A0j

ai+1

gj+1

aj

0
Bj+1

Bj+1

pj

qj+1

aj+1

Figure 3: Induction step in the proof of Lemma 6.3

7 Structural properties of a minimal circuit
In this section we analyze a minimal circuit in H + under certain conditions and we derive properties
of H + . We later use them to prove the correctness of the algorithm.
Let S be a set of pairs in V (H + ). Let Sb denote the set of pairs in H + that are reachable from S.
Note that Sb includes S. We call Sb the out-section of S. Let (a0 , a1 ), (a1 , a2 ), . . . , (an−1 , an ), (an , a0 )
b We say this circuit is minimal if there is no path from a pair in S that can reach
be a circuit in S.
to (ar , ar+1 ) to any of (ai , aj ), i 6= j − 1, r, i, j = 0, 1, 2, . . . , n.
Let S be a set of pairs in H + . For a pair (x, y) ∈ H + we may or may not have a path from
another pair in S to (x, y) with a positive net value. If such a path exists we call (x, y) a z-pair
with respect to S and associate to each z-pair (x, y) a path Zx,y of net value one constricted from
below and ending at (x, y).
Lemma 7.1 Let S be a set of pairs in H + and suppose Sb has a minimal circuit (a0 , a1 ), (a1 , a2 ), . . . ,
b There exists an(an−1 , an ), (an , a0 ) (n > 1) such that each (ai , ai+1 ) is a z-pair with respect to S.
0
0
0
0
0
0
b and walks Pi , Qi , i = 0, . . . , n, in H,
other circuit (a0 , a1 ), (a1 , a2 ), . . . , (an , a0 ) of the pairs in S,
such that Pi , Qi are walks of net length one, constricted from below, Pi from a0i to ai , Qi from a0i+1
to ai+1 , and such that Pi and Qi are congruent and avoid each other.
0 ) ∈ S
b to (ai , ai+1 ). We will find
Proof: Let Zi = Zai ,ai+1 , 1 ≤ i ≤ n, be a path from (p0i , qi+1
0
0
0
n vertices ai from amongst the 2n vertices pi , qi which satisfy the conclusion. As an intermediate
b For any i,
step, we will find n vertices a∗i of the 2n vertices pi , qi which also yield a circuit in S.
0
0
∗
0
∗
if Li−1 < Li we let ai = qi and ai = qi and if Li−1 ≥ Li we let ai = pi and ai = p0i . We first
prove that each pair (a∗i , a∗i+1 ) in the circuit (a∗0 , a∗1 ), (a∗1 , a∗2 ), . . . , (a∗n , a∗0 ) can be reached from the
corresponding pair (ai , ai+1 ).
First consider the case that Li−1 < Li < Li+1 , in which we have (a∗i , a∗i+1 ) = (qi , qi+1 ). We refer
to Figure 4 to summarize the steps of the proof. First of all, we find corresponding vertices r, s so
that the green walks C from r to ai and D from s to ai+1 have net length Li .
Then Corollary 6.2 is applied to the four green walks A, B, C, D, to conclude that A, B avoid
each other and C, D also avoid each other. Moreover A, C have a common pre-image that avoid

16

u

r

v

B

A

C

ai−1

pi−1 q i
ai
p’i−1 q’i

s

pi
p’i

qi+1
q’i+1

ai+1

D

ai+2

Figure 4: walks A, B avoid each other and walks C, D avoid each other

each other and B, D have common pre-image that avoid each other. Now we can use Lemma 6.3
on the suggested blue walks. Specifically, the blue walk from pi to u, then taking A to ai and then
use A−1 + A again; the blue walk from qi+1 to v followed by B + C −1 + C; and the blue walk
C −1 + C + C −1 + C, and the blue walk D−1 + D + D−1 + D (see Figure 4). We conclude that
the walk A−1 + A and the walk B −1 concatenated with the walk from v to qi+1 have common preimages that avoid each other. Thus (ai , ai+1 )
(ai , qi+1 ) and (ai+1 , ai+2 )
(qi+1 , ai+2 ). Then
using similar arguments to the red walks of height Li−1 we conclude that (ai , qi+1 )
(qi , qi+1 )
and from (ai−1 , ai )
(ai−1 , qi ). This allows us to replace ai by qi and ai+1 by qi+1 in the circuit
(a0 , a1 ), . . . , (an , a0 ). (The proof in case Li−1 < Li < Li+1 is symmetric.)
If Li ≥ Li−1 and Li ≥ Li+1 , then (a∗i , a∗i+1 ) = (qi , pi+1 ) and (a0i , a0i+1 ) = (qi0 , p0i+1 ). Lemma
6.3 can be similarly used to conclude that (ai , ai+1 )
(qi , pi+1 ). In fact, by an argument identical to the one in the proof of Lemma 7.3, as illustrated in the Figure 5, one can show, that
0 ) are all reachable from each other, in fact that the paths depicted in
(ai , ai+1 ), (pi , qi+1 , (p0i , qi+1
Figure 5 (of net length zero, constricted from below) avoid each other.
In case Li ≤ Li−1 and Li ≤ Li+1 , we have (a∗i , a∗i+1 ) = (pi , qi+1 ), and by using Lemma 6.3 in a
fashion similar to the above proofs, we conclude easily that there are the walks from ai to a∗i and
from ai+1 to a∗i+1 ) that avoid each other and are of net length zero, constricted from below.
We now show that a0i a∗i+1 and a0i+1 a∗i are not arcs of H, completing the proof of the Lemma. In
fact, this has already been observed (by appealing to the proof of Lemma 7.3) for the i which have
Li ≥ Li−1 and Li ≥ Li+1 .
If Li−1 < Li < Li+1 . In fact, we assume Li−1 < Li < Li+1 < . . . Li+j ≥ Li+j+1 for some j ≥ 1.
Note that this means that a∗i = qi , a∗i+1 = qi+1 , . . . , a∗i+j−1 = qi+j−1 , a∗i+j = qi+j , a∗i+j+1 = pi+j+1 .
We first note that since Li+j ≥ Li+j−1 and Li+j ≥ Li+j+1 we already know that p0i+j+1 qi+j is not
0 p
0
an arc of H. By symmetry, qi+j
i+j+1 is also not an arc of H. Next we argue that pi qi+2 is not
0 )
(a∗i+2 , a∗i+1 ) contradicting the minimality of n. This implies
an arc of H as otherwise (p0i , qi+1
0
0 )
(pi , qi+2 ) and eventually (qi , qi+2 ) =
that qi+1 qi+2 is not an arc of H, as otherwise (p0i , qi+1
∗
∗
(ai , ai+2 ) (using Lemma 6.3 on suitable portions of the walks). The same arguments imply that
0 q
0
0
p0i+1 qi+3 6∈ A(H) and qi+2
i+3 6∈ A(H), and so on until pi+j−2 qi+j 6∈ A(H) and qi+j−1 qi+j 6∈ A(H).
0
(These will all be used later.) Now we proceed to show that qi+j qi+j−1 is not arc of H, otherwise

17

u
g

g’

A
pi−1
p’i−1

Wi

C’
B’ C

B

A’

a i−1

h

v

qi
q’i

h’
D

ai

D’
E’ E
ai+1

F
F’

pi+1 qi+2
p’i+1 q’i+2

ai+2

Zi+1

Z i−1

Figure 5: Illustration of the proof of Lemma 7.1

0 , p0
∗
∗
∗
∗
(qi+j
i+j+1 ) (which we have shown to be reachable from (ai+j , ai+j+1 )) can reach (ai+j−1 , ai+j+1 )
0
0
∗
because qi+j pi+j+1 = qi+j ai+j+1 is not an arc of H. This contradicts the minimality of n. Note
0 q
0
that now we have both qi+j
i+j−1 6∈ A(H) and qi+j−1 qi+j 6∈ A(H). The first fact implies that
(a∗i+j−1 , a∗i+j )
(a0i+j−1 , a0i+j ). The second fact implies that we can repeat the argument to
0
conclude that qi+j−1 qi+j−2 6∈ A(H), and continue the argument in this way, eventually showing
0 q 6∈ A(H) and a0 a∗
0
that a0i+1 a∗i = qi+1
i
i i+1 = qi qi+1 6∈ A(H).
It remains to consider those i that have Li ≤ Li−1 and Li ≤ Li+1 . In this case, a∗i = pi
and a∗i+1 = qi+1 . If Li+1 < Li+2 , then a∗i+2 = qi+2 , and we can use the previous argument to
0 q
0
0
conclude that qi+1
i+2 and qi+2 qi+1 are not arcs of H. This implies that qi+1 pi is also not an arc
0
0
of H, otherwise the walk qi+1 , qi+1 , pi avoids the walk qi+2 , qi+2 , qi+2 and hence the pair (pi , qi+2 )
= (a∗i , a∗i+2 ) ∈ Sb , contradicting the minimality of n.
On the other hand, if Li+1 ≥ Li+2 we have a∗i+2 = pi+2 and we use another previous case to
0 p
0
conclude that qi+1
i+1 and pi+2 qi+1 are not arcs of H, and hence there is walk from qi+1 to pi that
b again yielding
avoids a walk from pi+2 to itself, thereby the pair (pi , pi+2 ) = (a∗i , a∗i+2 ) is also in S,
a contradiction.


Each unbalanced strong component C of H + contains a directed cycle D of non-zero net value
r, corresponding to two closed walks D1 , D2 in H, with D1 avoiding D2 , each of net length r.
Note that r could be positive or negative. As observed earlier, if r > 0, then any extremal vertex
(often called extremal pair) (x, y) of D must initiate an infinite directed walk W = w1 , w2 , . . . with
w1 = (x, y), continuously winding around D in the positive direction, such that the net values of
any portion W [w1 , wt ] are non-negative (the net values are constricted from below) and unbounded
(for any k > 0 some W [w1 , wt ] has net value k).
Theorem 7.2 Let T be a subset of unbalanced pairs such that if (a, b) ∈ T then (b, a) 6∈ Tb.
Suppose Tb contains a circuit and let (a0 , a1 ), (a1 , a2 ), . . . , (an , a0 ) be a minimal circuit in Tb .
Then the following statements hold.

18

1. n > 1 and there exists a circuit (b0 , b1 ), (b1 , b2 ), . . . , (bn−1 , bn ), (bn , b0 ) consisting of extremal
pairs.
2. Each (ai , ai+1 ) can be reached from the corresponding (bi , bi+1 ) by a symmetric directed walk
in H + with positive net value.
3. There are infinite walks Pi , 0 ≤ i ≤ n, starting at bi such that Pi , Pj , 0 ≤ i < j ≤ n, avoid
each other.
Proof: For contradiction suppose n = 1. This means (a, b)
(a0 , a1 ) for some (a, b) ∈ T and
0
0
0
0
(a , b )
(a1 , a0 ) for some (a , b ) ∈ T Now by skew symmetry we have (a0 , b0 )
(b, a), a contradiction unless (a0 , a1 ) = (a, b) and (a1 , a0 ) = (a0 , b0 ) and hence (a, b), (b, a) ∈ T , again a contradiction.
Therefore n > 1.
For each i, let Ci be the strong component of H + containing an extremal pair in S where (ai , ai+1 )
is reached from Ci , and let Di be a directed cycle in Ci .
Claim 7.3 We may assume each (ai , ai+1 ) is a z-pair with respect to Tb.
0 ) ∈ T
b to (ai , ai+1 ) which is constricted from
Proof: Let Zi = Zai ,ai+1 be a path from (p0i , qi+1
below and has net value one. Consider first a subscript i such that Di has positive net value. Then,
as observed above, there is an infinite directed walk W continuously winding around Di in the
positive direction, whose net values are constricted from below and unbounded. By following W
as far as necessary and then following a path that leads from Ci to (ai , ai+1 ) (such a path exists
both when (ai , ai+1 ) is in Ci or reachable from Ci ), we obtain a directed walk Wi in H + that has
0 ) be the last vertex on W such that the net value
values constricted from below. We let (p0i , qi+1
i
0 ), (a , a
0 0
of Wi [(p0i , qi+1
i i+1 )] is one, and we set Zi = Wi [(pi , qi+1 ), (ai , ai+1 )]. Let Li be the maximum
0 ), (x, y)] for any (x, y). Note that L
net value of a prefix of Zi , i.e., of a directed walk Zi [(p0i , qi+1
i
could be one, in case the values of Zi are also constricted from above, i.e., Zi is just one arc in H + .
We emphasize for future reference that in this case the directed walk Zi arises from Wi that
started on the cycle Di .
A similar argument applies to a subscript i such that Di has negative net value, but following
the directed walk W discussed above (unbounded and non-positive) and then a path from Di to
(ai , ai+1 ), we obtain a directed walk Wi in H + that has values constricted from above but not
0 ) be the last vertex on W
constricted from below. Indeed, in such a case we can again let (p0i , qi+1
i
0
0
0 ), (a , a
such that the net value of Wi [(pi , qi+1 ), (ai , ai+1 )] is one and set Zi = Wi [(p0i , qi+1
)].
i i+1
Suppose next that there are two subscripts i, i + 1 (addition modulo n) such that both Di and
Di+1 have negative net values, and both Wi and Wi+1 have constricted values, from some pairs
(u, v), (w, x) ∈ Sb to (ai , ai+1 ), (ai+1 , ai+2 ) respectively. We may assume that the pairs (u, v), (w, x)
are on the cycles Di , Di+1 , and that the net values of Wi , Wi+1 are the same (by choosing for their
starting vertices a suitable extremal vertex on each Di ). In this context, Corollary 6.2 applies to
the four walks A, B, C, D in H corresponding to Wi , Wi+1 , and we conclude that, in particular,
A, B avoid each other and C, D avoid each other. This implies that the reverse traversal of the
cycles Di , Di+1 is also a cycle in H + , of positive net value, and we can proceed as in the case when
Di , Di+1 had positive net value (see Figure 6 ).

19

u

v
B1
A1

A2

u’
B2
C
C2 1

D1

D2

p’i q’i

p’
q’i−1
i−1
ai
pi−1 qi−1

ai−1

v’

pi

ai+1

qi

Figure 6: Claim 7.3 when Di , Di+1 have positive net value
u
g

g’

A
pi−1
p’i−1

Wi

C’
B’ C

B

A’

a i−1

h

v

qi
q’i

h’
D

ai

D’
E’ E
ai+1

F

F’
pi+1 qi+2
ai+2
p’i+1 q’i+2
Zi+1

Z i−1

Figure 7: Claim 7.3 when Di−1 , Di+1 have positive net value and Di has negative net value

Thus it remains to consider the case when Di has negative net value, and the values of Wi
are constricted (both from below and from above), and Di−1 , Di+1 have positive net values. We
illustrate this part of the proof in Figure 7. Each directed walk in H + is depicted as two walks in
H where the first avoids the second. (The avoided arcs are depicted as dotted lines.) We show in
the figure 7 the starting vertex (p0i−1 , qi0 ) of Zi−1 , its ending vertex (ai−1 , ai ), as well as the starting
0 ) of Z
vertex (p0i+1 , qi+2
i+1 , and its ending vertex (ai+1 , ai+2 )). In the illustration we assume neither
Zi−1 nor Zi+1 is constricted from above. (The proof in the cases where one or both are constricted
is similar and easier.) Without loss of generality, we assume that Li−1 ≥ Li+1 as depicted. As
shown, we let (pi−1 , qi ) be the second vertex of Zi−1 and (pi+1 , qi+2 ) the second vertex of Zi+1 . We
also show a constricted directed walk Wi ending in (ai , ai+1 ). We assume (g, h) is the last vertex on
0 ), (g, h)], and (g 0 , h0 ) the last vertex
Zi−1 that maximizes the net value of the prefix Zi−1 [(p0i−1 , qi−1
0
0
of Wi so that Zi−1 [(g, h), (ai−1 , ai )] and Wi [(g , h ), (ai , ai+1 )] have the same net values. (Note that
both these directed walks have constricted values.) The directed walk Zi−1 in H + corresponds
to two walks p0i−1 + A + A0 , qi0 + B + B 0 in H, as depicted, where the first avoids the second, in
particular A avoids B and A0 avoids B 0 . (A is the portion from pi−1 to g and A0 the portion from
g to ai−1 , and similarly for B). Now we claim the following facts.
1 The walks A0 , B 0 , C 0 , D0 have common pre-images that avoid each other, except for the pre-

20

images of B 0 and C 0
2 The walks A0−1 + A0 and B 0−1 + B −1 have common pre-images that avoid each other
3 The pairs (ai−1 , ai ) and (ai−1 , qi ) are reachable from each other
4 The walks B 0−1 + B −1 and D + D0 have common pre-images that avoid each other
5 The pairs (ai , ai+1 ) and (qi , ai+1 ) are reachable from each other
Item 1 follows directly by Lemma 6.1 because the minimality of the circuit (a0 , a1 ),
(a1 , a2 ), . . . , (an , a0 ) implies that (ai−1 , ai+1 ) or (ai+1 , ai ) or (ai , ai−1 ) can not be in Tb.
Therefore Lemma 6.3 applies to the walks A + A0 + A0−1 + A0 , B + B 0 + C + C 0 , D + D0 + D + D0 ,
using the same minimality arguments, verifying items 2 and 4. Items 3 and 5 follow from 2 and 4.
Items 3 and 5 imply that we can replace ai by a0i = qi and obtain another circuit of pairs
(a0 , a1 ), (a1 , a2 ), . . . , (ai−1 , a0i ), (a0i , ai+1 ), . . . , (an , a0 )
in Tb. A similar argument shows that we may replace ai+1 by a0i+1 = pi+1 . In the rest of the proof
we assume that we have made the replacement, i.e., that ai = qi , ai+1 = pi+1 .
We now show that, in the new circuit, the path Zi actually exists, namely, that the (single-arc)
walks qi0 qi and p0i+1 pi+1 avoid each other, and hence the new (ai , ai+1 ) and (qi0 , p0i+1 ) are reachable
from each other. First, we observe that p0i−1 pi+1 is not an arc, otherwise (p0i−1 , qi0 )
(ai+1 , ai ),
0
0
contradicting the minimality of the circuit. Then qi pi+1 is not an arc, otherwise (pi−1 , qi0 )
(ai+1 , ai+1 ), yielding the same kind of contradiction. Finally, p0i+1 qi is not an arc, otherwise (ai , qi+2 )
0 ), and hence (p0 , q 0 )
is reachable from (p0i+1 , qi+2
(ai , ai+2 ), by one more application of Lemma
i+1 i+2
6.3.

Having the vertices p0i , qi0 , i = 0, 1, . . . , n, allows us to modify the circuit (a0 , a1 ), (a1 , a2 ), . . . ,
(an , a0 ) one step towards satisfying the Theorem 7.2.
Lemma 7.1 has a stronger version as follows:
Claim 7.4 For every integer k > 0, there exists circuit (ak0 , ak1 ), (ak1 , ak2 ), . . . , (akn , ak0 ) of pairs in Tb,
and walks Pik , Qki , i = 0, . . . , n, in H such that each pair Pik , Qki are walks of net length k constricted
from below, Pik is from aki to ai , Qki from aki+1 to ai+1 , such that Pik and Qki are congruent and
avoid each other. Moreover, the walk Pik+1 is a suffix of the walk Pik for each k, and similarly for
Qk+1 .
By reversing the walks Pik , Qki and increasing k arbitrarily high, we prove the following fact.
Claim 7.5 There exist infinite walks Si , Ti , i = 0, 1, . . . , n in H, where Si starts in ai and Ti starts
in ai+1 such that Si , Ti are congruent and avoid each other. Moreover, the net lengths of these
walks are unbounded from below.
Consider the set of pairs (s, t) of corresponding vertices in Si , Ti ; since Si , Ti avoid each other,
these pairs (s, t) are all from the same strong component of H + as (ai , ai+1 ) (which we called Ci ).
Therefore, eventually the same pair (s, t) is repeated. This means that each Ci contains a circuit of

21

positive net value. Hence, we may assume that each cycle Di (our unbalanced cycle of choice in the
component Ci ) is in fact of positive net value. Thus we can avoid the complications in the proof
of Lemma 7.3: the first alternative, that Di has positive net value, applies in all cases. This has
effect on the walks Pi , Qi , Pik , Qki and also Si , Ti above. In particular, the corresponding pairs (s, t)
of vertices on walks Si , Ti may be assumed to eventually reach the cycle Di , and then remain on
that cycle. This uses Lemma 7.3 in conjunction with Lemma 7.1, continually replacing the circuit
until we get a circuit (b0 , b1 ), (b1 , b2 ), . . . , (bn−1 , bn ), (bn , b0 ) until each (bi , bi+1 ) is on the cycle Di
in H + . Moreover, we can continue doing this until (bi , bi+1 ) is an extremal vertex of Di . (Recall
that there exist r extremal pairs, where r is the net length of Di .)
For future reference we note that we can reverse the walks Si , Ti .
Claim 7.6 There exist infinite walks Qi , Ri , i = 0, 1, . . . , n in H, where Qi starts in bi and Ri starts
in bi+1 such that Qi , Ri are congruent and avoid each other. Moreover, these walks are constricted
from below and their net lengths are unbounded from above.
It is important to note that the walks Qi , Ri are obtained by continuously following the cycle Di
in the positive direction.
By applying Corollary 6.3 to suitable (repeated) increasing prefixes of the walks Qi , Ri we can
easily conclude that they have pre-images, say Pi , that all avoid each other, except for the corresponding (intersecting) walks Qi , Ri−1 . In particular we obtain the following useful conclusion that
complete the proof of Theorem 7.2 (3) :
There are infinite walks Pi , i = 0, 1, . . . , n, in Di , starting in bi , that all avoid each
other.

Corollary 7.7 Let T be a subset of unbalanced pairs such that if (a, b) ∈ T then (b, a) 6∈ Tb.
Suppose Tb contains a circuit and let (a0 , a1 ), (a1 , a2 ), . . . , (an , a0 ) (n > 1) be a minimal circuit
in Tb . Then there is no path in H + from (ai , ai+1 ) to any of (aj , aj+1 ), (aj+1 , aj ), i 6= j.
Proof: By Theorem 7.2 both pairs (bi , bi+1 ), (bj , bj+1 ) are extremal pairs on cycles Di and Dj
respectively. Let W be the directed walk from (bi , bi+1 ) to (bj , bj+1 ) we may assume that Di is
constricted from above. Otherwise we add to the beginning of W a directed walk W 0 obtained by
going around the cycle Di (in negative direction) sufficiently many times and adding to the end of
W directed walk W 00 obtained by going around the cycle Dj (in negative direction) sufficiently many
times (this is possible since Pi , Pi+1 avoid each other, and Pj , Pj+1 avoid each other). Let W =
−1 0
(X1 , X2 ). Consider two vertices p0 ∈ Pj+1 and q 0 ∈ Pj+2 . Where the portion of A0 = Pj+1
[p , bj+1 ]
−1
0
0
and B = Pj+2 [q , bj+2 ] are congruent (avoid each other) and have the same net value as W . Now
by Corollary 6.2 we conclude that X1 and X2 avoid each other. Therefore (bi , bi+1 ) and (bj , bj+1 )
are in the same strong component. Thus by We may assume that Di is the cycle that contains both
(bi , bi+1 ), (bj , bj+1 ) (we replace Di by a cycle that goes around Di (in positive direction) sufficiently
many times and then it follows W to (bj , bj+1 ) and then going around Dj once and then back to
(bi , bi+1 ) on W −1 ). Observe that Di now has net value greater than 1.
By Theorem 7.2 (2) the walks Pi and Pj around Di avoid each other and we can apply Corollary
4.4 to conclude that some component of H + contains a circuit, a contradiction. By similar argument
from from the previous proposition we have the following.

22

There is no path in H + from (ai+1 , ai ) to (ai , ai+1 ), and in particular there is no path from
(a0 , an ) to (an , a0 ).

The following proposition will be used in the last section. Recall that we have denoted by Ci the
(strong) component of H + containing the pair (ai , ai+1 ). A digraph is symmetric if for each arc uv
the arc vu is also present.
Proposition 7.8 Let T be a subset of unbalanced pairs such that if (a, b) ∈ T then (b, a) 6∈ Tb.
Suppose Tb contains a circuit and let (a0 , a1 ), (a1 , a2 ), . . . , (an , a0 ) (n > 1) be a minimal circuit
in Tb . Then each component Ci is a symmetric digraph.
Proof: We will show that every directed walk W 0 in Ci from some (c, d) to (ai , ai+1 ) consists
of two walks, X from c to ai and Y from d to ai+1 , that avoid each other. Since every arc of
Ci lies on a such a walk, this proves the Proposition. By Theorem 7.2 (2), there exists a circuit
(b0 , b1 ), (b1 , b2 ), . . . , (bn , b0 ) of extremal pairs where (bi , bi+1 ), (ai , ai+1 ) are in the same component
Ci .
Recall that (bi , bi+1 ) lies on Di (which is a closed walk of positive net value). We also note by
Theorem 7.2 (3) that Pi , Pi+1 are obtained by repeatedly following cycle Di in positive direction
(see also Claim 7.6 ).
Consider a directed walk W from (bi , bi+1 ) to (c, d) in Ci that has a negative net value and it is
constricted from above. Such a directed walk is obtained by starting at (bi , bi+1 ) and going around
the cycle Di in negative direction sufficiently many times and then going to (c, d). Now consider
the directed walk W 0 going from (c, d) to (bi , bi+1 ) and then following the directed walk W 00 around
the cycle Di in the negative direction, so that W W 0 W 00 is constricted and has negative net value,
(Again this can be obtained by going around Di in negative direction sufficiently many times). The
directed walk W W 0 W 00 gives two constricted walks A, B from some bi , bi+1 to bi , bi+1 respectively,
where A avoids B. Now let C, D be two walks from p, q to bi+1 , bi+2 respectively, that avoid each
other and have the same negative net value as A. (We may assume p ∈ Pi+1 and p ∈ Pi+2 ). Now
by Corollary 6.2 we conclude that A, B avoid each other and hence the walks X and Y constituting
W 0 avoid each other. This implies that Ci is symmetric.


8 Balanced pairs and minimal circuits
A strong component of H + is balanced if every closed directed walk in that component has net
value zero, i.e., the same number of positive and negative arcs. A pair of H + is called balanced if
it lies in a balanced strong component.
Let H ∗ be the sub-digraph of H + induced by balanced pairs. The pairs in H ∗ can be assigned
levels so that if (a, b)(c, d) is a positive arc in H + , then the level of (c, d) is one more than the level
of (a, b), and if (a, b)(c, d) is a negative arc in H + , then the level of (c, d) is one less than the level
of (a, b).
Definition 8.1 We say a set T of the pairs in H + is good with respect to level ` if it has at least
one pair of H ∗ on level `
and for all pairs (x, y) of H ∗ with level `0 < ` exactly one of the (x, y), (y, x) belongs to T .

23

Recall that Tb is the set of pairs that are reachable from T .
Theorem 8.2 Let T be a good set with respect to level `.
Suppose Tb contains a circuit, and let (a0 , a1 ), (a1 , a2 ), . . . , (an , a0 ) be a minimal circuit in Tb .
Then one of the following statements holds.
1. n = 1 and there exists (a, b) ∈ T such that (b, a) ∈ Tb
2. n > 1 and if (ai , ai+1 ), (ai+1 , ai+2 ) are z-pairs with respect to Tb then there is no path in H +
from (ai , ai+2 ) to any of (ai+1 , ai ), (ai+2 , ai+1 ), and (ai+2 , ai ).
Proof: If n = 1 then there exists (a, b), (a0 , b0 ) ∈ T such that (a, b)
(a0 , a1 ) and (a0 , b0 )
0
0
0
0
(a1 , a0 ). Now (a , b )
(b, a). Therefore (a , b )
(b, a) and hence (a, b) ∈ T and (b, a) ∈ b(T ).
It is easy to see that if n > 1 then the circuit is on level ` of H ∗ , i.e. the pairs of the circuit that
belong to H ∗ are on level `. First we note that (ai , ai+2 ) is not a z-pair. Otherwise according to
assumptions for T , (ai , ai+2 ) ∈ Tb, and hence we get a shorter circuit.
0 ) be the first vertex on
We may assume Li ≤ Li+1 . Now we show that L < Li+1 − 1. Let (p0i , qi+1
Zai ,ai+1 and (pi , qi+1 ) be the second vertex and we may assume that Zai ,ai+1 [(pi , qi+1 ), (ai , ai+1 )] has
net value zero and constricted from below (Note that we use the notation used in the Lemma 7.1 and
most of the argument for this case is similar to argument in Lemma 7.1). By the argument similar
0 )(p , q
to the one in Lemma 7.1 it follows that p0i+1 pi is not an arc of H (as otherwise (p0i+1 , qi+2
i i+2 ) ∈
+
A(H ) and also (pi , qi+2 ), (ai , ai+2 ) are in the same strong component and hence Zai ,ai+2 exists,
0 )(q
+
a contradiction). Moreover, p0i qi+2 6∈ A(H) as otherwise (p0i , qi+1
i+2 , qi+1 ) ∈ A(H ). Observe
that as it shown in Lemma 7.1 (ai+1 , ai+2 ), (qi+1 , qi+2 ) are in the same strong component of H + .
0 )
0 )
Now (p0i , qi+1
(ai+2 , ai+1 ), and (p0i , qi+1
(ai+1 , ai+2 ). Therefore for some (x0 , y 0 ) ∈ S we have
0
0
0
0
(x , y )
(y , x ), a contradiction.
0 ) ∈ A(H + ) (since p0 p is not an arc). Now (p0 , q 0 ) and (p0 , q 0 )
Note that (pi , qi+1 )(p0i , qi+1
i+1 i
i i+1
i+1 i+2
0 ) ∈ S)
b
b or (q 0 , p0 ) ∈ Sb (the
are in S since they are on a lower level than ` and therefore (p0i , qi+2
i+2 i
former is not possible as it would imply a circuit of level `0 < ` in T , a contradiction to T being a
0 ) ∈ S.
b Now (p0 , q 0 )(pi , qi+2 ) ∈ A(H + ) and (as shown in Lemma
good set). Thus we have (p0i , qi+2
i i+2
0 )
7.1, (pi , qi+2 ), (ai , ai+2 ) are in the same strong component of H + ). Therefore (p0i , qi+2
(ai , ai+2 ).
Thus (ai , ai+2 ) is a z-pair, a contradiction.
We note that if (ai+2 , ai ) is a z-pair then we according to Lemma 7.1 there is a circuit on
a lower level of H ∗ . Therefore (ai+2 , ai ) is not a z-pair. We also note (ai , ai+2 ) 6
(ai+1 , ai )
as otherwise (ai , ai+1 )
(ai+2 , ai ) and hence (ai+2 , ai ) is a z-pair , a contradiction. Similarly
(ai , ai+2 ) 6 (ai+2 , ai+1 ). Now suppose (ai , ai+2 ) ∈ T and there exits a path W from (ai , ai+2 ) to
(ai+2 , ai ). Since neither of (ai+2 , ai ), (ai , ai+2 ) is a z-pair, W is constricted from below.
Let L0 be the height of Zai ,ai+1 and L1 be the height of Zai+1 ,ai+2 and assume L0 ≤ L1 (the
argument for L0 > L1 is symmetric).
As we showed we have L < L1 − 1. Now by applying the Lemma 6.2 on suitable portion of
Zai+1 ,ai+2 and W we conclude that A0 , A2 avoid each other where W = (A0 , A2 ). This would mean
(ai , ai+2 ) and (ai+2 , ai ) are in the same strong component of H + , a contradiction to the choice of
T.

The stronger version of Theorem 8.2 is the following Corollary.

24

Corollary 8.3 Let T be a good set with respect to level `.
Suppose (a1 , a2 ), (a2 , a3 ), . . . ,
(aj−1 , aj ), 1 < j − 1 are z-pairs in T . Then there is no path in H + from (ai , at ), 1 ≤ i < t ≤ j, to
(ar , ai ), 1 ≤ i < r ≤ j.
Proof: By comparing the height of the path from (ai , at ) to (ar , ai ) and the height of Zai ,ai+1 , Zat−1 ,at ,
Zar−1 ,ar , and applying similar argument as in the proof of Theorem 8.2, we get a contradiction. 
Following the proof of the Lemma 7.1 one can obtain the following corollary.
Corollary 8.4 Let S be a set of pairs. Suppose Sb contains a circuit and let (a0 , a1 ), (a1 , a2 ), . . . ,
b
(an , a0 ) (n > 1) be a minimal circuit in S.
b
If (ai , ai+1 ) is a z-pair with respect to S then let (pi , qi+1 ) be the second vertex on Zai ,ai+1 otherwise
let Xi be a constricted directed walk from below of net value zero from (pi , qi+1 ) ∈ S to (ai , ai+1 )
(Xi could be just a path in strong component containing (ai , ai+1 ).
Then there exists another circuit (a000 , a001 ), (a001 , a002 ), . . . , (a00n , a000 ) of pairs, and walks Pi0 , Q0i , i =
0, . . . , n, in H, such that Pi0 , Q0i are walks of net length zero, constricted from below, Pi0 from a00i to
ai , Qi from a00i+1 to ai+1 , and such that Pi0 and Q0i are congruent and avoid each other. Here each
(a00i , a00i+1 ) is either (pi , qi+1 ) or (qi , pi+1 ) or (qi , qi+1 ) or (pi , pi+1 ).
Corollary 8.5 Let S be a set of pairs. Suppose Sb contains a circuit and let (a0 , a1 ), (a1 , a2 ), . . . ,
(an , a0 ), (n > 1) be a minimal circuit in Sb Let W1 be a directed walk from (p, q) ∈ S to (ai , ai+1 )
of net value zero and let W2 be a directed walk from (p, q) to (ai+1 , ai+2 ) of net value zero. Then
at least one of the W1 , W2 is not constricted from below.
Proof: For contradiction W1 and W2 both are constricted from below. We may assume L1 the
height of W1 is at most L2 ; the height of W2 . Now by Corollary 8.4 and the proof of the Lemma
7.1 (ai , ai+1 ), (q, q) are in the same strong component, a contradiction. Similarly if L2 < L1 then
(ai , ai+1 ) and (p, p) are in the same strong component of H + , a contradiction.

Lemma 8.6 Let x, y, z be three vertices such that there exist a path Wx in H + from (y, x) to (x, y)
and there exists a path Wy in H + from (z, y) to (y, z) where both Wx , Wy are constricted from below
and have net value zero.
Then there is no path Wz in H + from (x, z) to (z, x) which is contracted from below and has net
value zero.
Proof: Suppose this is not the case and Wz exists. Up to symmetry suppose Lz the height of Wz
is bigger than Ly the height of Wy respectively.
We observe that (x, z) 6 (x, y) and (x, z) 6 (y, z). For contradiction suppose (x, z)
(y, z). Let
T = {(x, y), (y, z), (x, z)} and now there is a circuit (x, y), (y, z), (z, x) in Tb. Since (x, z)
(z, x)
and (x, z)
(y, z), we get a contradiction by Corollary 8.5. Similarly (x, z) 6 (x, y). These would
also imply that (x, z) 6 (y, x) and (x, z) 6 (z, y). By the symmetry (y, x) 6 (y, z), (y, x) 6 (z, x)
and (z, y) 6 (x, y), (z, y) 6 (z, x).
Let Wz = (Z, Z 0 ) and Wy = (Y, Y 0 ) and let (g, h) be a vertex on Wz where Wz [(g, h), (z, x)] is
constricted from above and has height −Ly . Let Wz [(g, h), (z, x)] = (A2 , A0 ). Now by applying
Corollary 6.2 on Y, Y 0 , A2 , A0 we conclude that Y 0 , Y 0 avoid each other. This would imply that
(y, z) and (z, y) are in the same strong component of H + , contradiction.


25

9 Choosing pairs of unbalanced components
We say a pair (x, y) in an unbalanced strong component of H + is half extremal if at least one of
the (x, y), (y, x) is extremal.
Lemma 9.1 Let U = {u1 , u2 , . . . , um } and let R be a set of ordered pairs (ui , uj ), i < j each being
half extremal pair in H + . Let Rk be a subset of R consisting of all pairs (ui , uj ) ∈ R with k ≤ i < j.
b has no circuit.
Suppose that for each Rk , uk is a source. Then R
b contains a circuit and let (a0 , a1 ), (a1 , a2 ), . . . , (an , a0 ) be a
Proof: For contradiction suppose R
b
minimal circuit in R.
Since each Ri has a source, it is easy to see that n > 1 (c.f. the proof of Theorem 7.2). According
to the Theorem 7.2 there exists another circuit (b0 , b1 ), (b1 , b2 ), . . . , (bn , b0 ) where each (bi , bi+1 )
is extremal and lies in the directed cycle Di in a strong component of H + . By Theorem 7.2,
(ai , ai+1 ), (bi , bi+1 ) are in the same strong component of H + .
By Theorem 7.2 (2) we observe that for every i, j, (bi , bj ) is in an unbalanced component. Thereb as well,
fore if one of the b` ’s is a source for some Ri then it would mean we have (b` , b`+2 ) ∈ R
yielding a shorter circuit. Thus it remain to prove that we may assume one of the b` is a source.
Claim 9.2 At least one of the b` ’s is a source.
Proof: For contradiction none of the bi ’s is a source. Now each (bi , bi+1 ) is in some strong component Ci where it has an extremal pair (p, q) and p was a source for some Rj where j is the minimum
subscript. Now by Proposition 7.8 we may assume that (p, q) and (bi , bi+1 ) lies on the same cycle
Di . This can be achieved by starting from (bi , bi+1 ) and going around Di and then to (p, q) on the
path in Ci and then back on the same path (the arcs in Ci are symmetric by Corollary 7.8 ) to
(bi , bi+1 ) ).
Therefore by applying the Corollary 7.4 sufficiently many times (the net value between (p, q) and
(bi , bi+1 ) in Di ) we may assume that there exist another circuit such that (p, r) is one of the pair
of the circuit and (bi , bi+1 ) and (p, r) are in the same strong component. Since j is the minimum
subscript, there does not exist (q, p) ∈ R such that (q, p), (p, r) are the pairs of this new circuit.
This means that n = 1. In this case we have (p, r)
(a0 , a1 ) and (p, s)
(a1 , a0 ). Now by skew
symmetry we have (p, r)
(s, p) contradiction to p being a source for Rj .



This completes the proof of the lemma.

Lemma 9.3 Any set S of half extremal pairs such that (a, b) ∈ S implies that (b, a) ∈ S has a
source.
Proof: Let U be the set of vertices of H that appear, as a first or second coordinate, in pairs of
S. We use induction on |U |. We first observe that if |U | = 2, then S has a source. Indeed, suppose
U = {u1 , u2 }. If u1 is not a source for S, we must have both (u1 , u2 ), (u2 , u1 ) in S and (u2 , u1 )
reachable from (u1 , u2 ) in H + ; and if u2 is not a source for S we also must have (u1 , u2 ) reachable
from (u2 , u1 ) in H + . This would mean that u1 , u2 is an invertible pair, i.e., a circuit in a strong
component of H + , a contradiction. Thus there is a source for S.

26

Assume the statement for any set of size m and let U have m+1 elements say U = {u, u1 , u2 , . . . , um }.
For simplicity when we say x ∈ V (H) is a source for X ⊆ V (H), we mean x is a source for all
the pairs (a, b) ∈ S where a, b ∈ X. By induction hypothesis we may assume that u1 is a source
for U \ {u}. Observe that there exists 2 ≤ t ≤ m such that ui , 2 ≤ i ≤ t is a source for
{ui , ui+1 , . . . , um , u} and ui , t + 1 ≤ i ≤ m is a source for {ui , ui+1 , . . . , um } and u is a source for
{u, ut+1 , ut+2 , . . . , um }.
We say ui , ui+1 are not exchangeable if (ui , ui+1 ) ∈ S and (ui+1 , ui0 )
(ui , ui+1 ), 2 ≤ i +
1 < i0 ≤ m. If ui , ui+1 are exchangeable then we can assume that ui+1 is also source for
ui+1 , ui , . . . , ut , u, ut+1 , . . . , um . Otherwise we must have (ui+1 , ui )
(ui0 , ui+1 ) and hence ui , ui+1
are not exchangeable.
Now suppose u1 is not a source for U as otherwise we are done. This would mean (u1 , y)
(x, u1 )
where x, y ∈ U . Since u1 is a source for U \ {u}, either x = u or y = u. If y 6= u then we may
assume y = u` where ` is the smallest subscript.
We also assume u is not a source for U as otherwise we are done. Therefore there is a path in
+
H from (u, ur ) to (uj , u). Note either r = 1 or j = 1 as otherwise U \ {u1 } satisfies the condition
of the Lemma 9.1. Without loss of generality assume that (uj , u) is reachable from (u, u1 ) in H +
and j is the smallest subscript.
To summarize, one of the following happens :
1. (u, u1 )

(uj , u) and (u1 , u` )

2. (u, u1 )

(uj , u) and (u1 , u)

(u, u1 ).
(u, u1 ).

We prove (1) and the proof of (2) is similar. We may assume that j is a minimum subscript. Let
i1 < i2 < · · · < ik−1 < ik = j where uir and uir+1 , 1 ≤ r ≤ k are not exchangeable and uik−1 , uj
are not exchangeable and i1 is the smallest subscript. We may assume that i1 = 1 as otherwise we
can exchange ui1 −1 , ui1 .
No we may assume that ui2 is the minimum subscript. This would mean we assume that ui2 = u2
as otherwise we would exchange ui2 with ui2 −1 and continuing exchanging ui2 with the previous
element. By continuing this argument we may assume that ui3 is u3 and so on. Therefore we may
assume that i1 = 1, i2 = 2, . . . , ik = j and j = k. This means (u1 , u2 ), (u2 , u3 ), . . . , (uj−1 , uj ) ∈ S.
Case 1.
` ≤ j. Now there exists a circuit C1 = (u, u1 ), (u1 , u2 ), . . . , (uj−1 , uj ), (uj , u) in
T = {(u, u1 ), (u1 , u2 ), . . . , (uj−1 , uj ), (uj , u)}. Either C1 is a minimal circuit and has length more
than two or (ur , ur+s )
(u1 , u), 1 ≤ r ≤ j − 1. In the former case we have (ur , ur+s )
(u1 , u)
and we also have (u1 , u` )
(u, u1 ). These would imply that (ur , ur+s )
(u` , u1 ), a contradiction
b does not have a circuit according to Lemma 9.1. Here R = {(ui , uj ) ∈ S|i < j}.
to R
We continue by assuming C1 is minimal. This means we may assume (ur , ur+1 ) 6 (ui , ui0 ),
b However, there
i < i0 − 1. Moreover, (ur , ur+1 ) 6 (ui0 , ui ) as otherwise we have a circuit in R.
exists a path from (u1 , u` )
(u, u1 ). This is a contradiction by Lemma 7.7.
Case 2. ` > j. First suppose t ≤ `. We may assume that u is on the its latest position. By that
we mean u can not be exchanged with ut+1 . This means that u, ut+1 are not exchangeable and hence
similar to the previous case there exists a circuit (u1 , u), (u, ut+1 ), (ut+1 , ut+2 ), . . . , (u`−1 , u` ), (u` , u1 )

27

in T = {(u1 , u), (u, ut+1 ), (ut+1 , ut+2 ), . . . , (u`−1 , u` ), (u` , u1 )}. However, since (u1 , u)
get a contradiction by Lemma 7.7. Similar argument would apply when t > `.

(u` , u1 ), we


Proposition 9.4 In every execution of line 5 of the algorithm, the set S has a source. Thus we
can always execute line 8 of the algorithm. Moreover, after executing the loop in lines 9-11, the set
Vc will not contain a circuit.
Proof: Note that at each stage of the algorithm the set S in lines 5, 8 has all the remaining extremal
pairs and hence set T = S ∪ {(y, x)|(x, y) ∈ S} is the set of all remaining half extremal pairs. By
b where R
Lemma 9.3, T has a source and hence S has a source. Now it is easy to see that Vc is R
satisfies the conditions of Lemma 9.1. Therefore Vc will not contain a circuit.


10 Choosing pairs of balanced components
Proposition 10.1 Any set of pairs on a level ` of H ∗ has a source that respects transitivity in Vc .
Thus we can always execute line 16 of the algorithm. Moreover, after executing the loop in lines
17-19, the set Vc will not contain a circuit.
Proof: We first show the following fact. Let (u1 , u2 ), (u2 , u3 ), . . . , (um−1 , um ) be a chain of pairs
in Vc , each being a z-pair with respect to Vc . Then each ui , 1 ≤ i ≤ m, is a source for Ri
consisting of all pairs (ui , uj ), i < j ≤ m. Otherwise suppose ui is not a source for Ri . Therefore
(ui , uj )
(ur , ui ), i < j ≤ r. But this is a contradiction according to Corollary 8.3.
Let U = {u1 , u2 , . . . , um } ⊆ V (H) and let S1 be the set of all pairs (ui , uj ), 1 ≤ i < j ≤ m, of H +
such that (ui , uj ) is either a z-pair with respect to Vc or (ui , uj ) is on level ` of H ∗ . Suppose ui ∈ U ,
1 ≤ i ≤ m, is a source for Si consisting of all pairs in S1 that involves only vertices {ui , ui+1 , . . . , um }.
We also assume S1 has the following property. S1 contains all the pairs (x, y) that are z-pairs with
respect to Vc . It contains the pairs (x, y) where there is a chain (x, x1 ), (x1 , x2 ), . . . , (xt−1 , xt ), (xt , y)
of all z-pairs with respect to Vc and lastly it contains some pairs (x, y) on level ` of H ∗ with priority
given to (x, y) such that (y, x)
(y, x) if one exists.
c1 for any 1 ≤ i ≤ j ≤ m,
Claim 10.2 Let u0 be any vertex in V (H) \ U where (u0 , ui ), (uj , u0 ) 6∈ S
∗
(u0 , u1 ) is on level ` of H . Moreover if there are several such u0 we chose u0 such that (u1 , u0 )
(u0 , u1 ) if one exists. Let S2 be the set of all pairs (u0 , ui ), (uj , u0 ), 1 ≤ i, j ≤ m, each on level ` of
H ∗ . Then S2 has a source that respects transitivity in S1 .
Proof: For contradiction suppose there is no source for S2 . Since u0 is not a source, we have
(u0 , ur )
(uj , u0 ), 1 ≤ j ≤ r ≤ m. Suppose also u1 is not a source for S1 ∪ S2 . Therefore we have
(u1 , y)
(x, u1 ) where x, y ∈ {u0 , u1 , . . . , um }. Moreover since (u1 , ut ) ∈ S1 , 1 ≤ t ≤ m, y = u0
as otherwise (x, u1 ) ∈ S1 . Similarly x = u1 as otherwise when x = ut0 we have (u1 , ut0 )
(u0 , u1 )
and hence (u0 , u1 ) ∈ S1 . To summarize we have (u1 , u0 )
(u0 , u1 ) and (u0 , ur )
(uj , u0 ).
Case 1. j = 1. We have (u0 , ur )
(u1 , u0 ). Now we have (u0 , ur )
(u1 , u0 )
(u0 , u1 )
(ur , u0 ).
Now there is a circuit (u0 , u1 ), (u1 , u2 ), . . . , (ur−1 , ur ), (ur , u0 ) in S1 ∪ S2 . By definition (u1 , u3 ) ∈
S1 and hence we may assume r = 2 as otherwise we get a shorter circuit. To summarize, we have

28

(u0 , u2 )
(u1 , u0 )
(u0 , u1 )
(u2 , u0 ). Now there exists a circuit C = (u0 , u1 ), (u1 , u2 ), (u2 , u0 )
in S1 ∪ S2 . Note that we may assume at least one of the (u0 , u1 ), (u1 , u2 ), (u2 , u0 ) is not a z-pair
with respect to Vc . Otherwise we get a circuit on a lower level of Vc by Lemma 7.1. Moreover we
may assume at least one of the (u2 , u0 ), (u0 , u1 ) is not a z-pair with respect to Vc . First suppose
two of the three pairs in C are z-pairs with respect to Vc , say (u1 , u2 ), (u2 , u0 ). Now all the pairs of
Vc together with three pairs (u1 , u2 ), (u2 , u0 ), (u0 , u1 ) satisfies the conduction of Theorem 8.2. Since
(u1 , u0 )
(u0 , u1 ), we get a contradiction by Theorem 8.2. Now we may assume that at most one
of the pairs in C is a z-pair with respect with Vc . Note that this means none of (u2 , u0 ), (u0 , u1 )
is a z-pair. Therefore the path from (u1 , u0 ) to (u2 , u0 ) and the path from (u1 , u0 ) to (u0 , u1 ) are
constricted from below and have net value zero. Now let T be the set of (u1 , u2 ), (u2 , u0 ), (u1 , u0 ).
It is easy to see that circuit C is minimal in Tb and since (u1 , u0 )
(u2 , u0 ), and (u1 , u0 )
(u0 , u1 ),
we get a contradiction by Corollary 8.5.
Case 2. 1 < j ≤ r. First assume that r = j. Note that (u1 , uj ) ∈ S1 so in this case we may
assume j = 2. This means we have (u0 , u2 )
(u2 , u). If (u1 , u2 ) is not a z-pair with respect to Vc
then (u2 , u1 )
(u1 , u2 ) according to the choice of S1 (we have (u1 , u0 )
(u0 , u1 )) and we get a
contradiction by Lemma 8.6. So we may assume that (u1 , u2 ) is a z-pair with respect to Vc . Now
again by similar argument as in the proof of Lemma 8.6 (considering the height of the path from
(u2 , u1 ) to (u1 , u2 ) and the height of the path from (u1 , u0 ) to (u0 , u1 ) and the height of Zu1 ,u2 ) we
get a contradiction.
Therefore j < r. Note that (uj , ur ) ∈ S1 . Now we have the circuit (u0 , u1 ), (u1 , u2 ), . . . , (uj−1 , uj ),
(uj , ur ), (ur , u0 ) in S1 ∪S2 . Since (u1 , uj ) ∈ S, we may assume that (u0 , u1 ), (u1 , uj ), (uj , ur ), (ur , u0 )
is a circuit in S1 ∪ S2 . For simplicity we may assume j = 2. We note that W1 which is a path in
H + from (u1 , u0 ) to (u0 , u1 ) is constricted from below and has net value zero. Also Wr which a the
path in H + from (u0 , u2 ) to (ur , u0 ) is constricted from below and has net value zero.
First assume that the height of W1 is smaller than the height of Wr . Now consider the set
T = {(u1 , ur ), (ur , u0 ), (u0 , u2 ), (u1 , u0 )} and observe that there is a circuit (u1 , ur ), (ur , u0 ), (u0 , u1 )
in Tb. Similar to the proof of Lemma 8.6 (by applying Lemma 6.3) we conclude that (u0 , u1 ), (u0 , u1 )
are in the same strong component of H + , a contradiction. Therefore we may assume that the height
of W1 is greater than the height of Wr . Now consider the circuit (u0 , u1 ), (u1 , u2 ), (u2 , ur ), (ur , u0 )
is Tb where T = {(u1 , u2 ), (u0 , u2 ), (u1 , u0 )}. Therefore again by similar argument as in the proof
of Lemma 8.6, we conclude that the two walks of X, Y in H where Wr = (X, Y ) avoid each other.
By Lemma 6.3 on suitable portion of X, Y and the walks in H that give rise to W1 ( and the fact
that X, Y avoid each other), we conclude that (u2 , ur )
(u2 , u0 ), implying that (u2 , u0 ) ∈ Vc , a
contradiction.

The above Claim allows us to view remaining balanced pairs on level ` step by step and at each
step we show that there is a source for a subsets of unbalanced pairs on level `.
Claim 10.3 After executing the loop in lines 17-19, the set Vc will not contain a circuit.
Proof: Suppose by selecting a pair (x, y) on level ` at some stage of the algorithm (from line 17
to 19) we close a circuit (a0 , a1 ), (a1 , a2 ), . . . , (an , a0 ). We again suppose that up to this point no
circuits were created, and that n is as small as possible.

29

If (ai , ai+1 ) is not a z-pair then let (pi , qi+1 ) be a selected vertex on level ` where (pi , qi )
(ai , ai+1 ) and let Wi be a directed walk from (pi , qi+1 ) to (ai , ai+1 ) and we may assume that Wi
reaches to the maximum height.
If (aj , aj+1 ) is a z-pair then let (pj , qj+1 ) be a vertex on the level ` such that the portion of
0
Zaj ,aj+1 from (p0j , qj+1
) to (aj , aj+1 ) is constricted from below and has net value zero. Let Li be
the height of Wi and Lj be the height of Zjj ,jj+1 minus one.
Let (pr , qr ) be a pair where pr is the source. This means for every other (pj , qj ) the algorithm
selects Cr before Cj which contains (pj , qj ). Now as we argued in the unbalanced case and according
to Corollary 8.4 there exists another circuit (a∗0 , a∗1 ), (a∗1 , a∗2 ), . . . , (a∗n−1 , a∗n ), (a∗n , a∗0 ) where (a∗i , a∗i+1 )
is already chosen or is selected (belongs to Vc ). Note that {a∗0 , a∗1 , . . . , a∗n } is a subset of T =
{p0 , q0 , p1 , q1 , . . . , pn , qn }. However, according to the choice of p0 , p1 , . . . , pn , q0 , q1 , . . . , qn there must
be a source in T but this is a contradiction to having a source.


11 k-arc digraphs and k-min ordering
A k-min ordering of a digraph H is a partition of V (H) into k subsets V0 , V1 , . . . , Vk−1 , and a
linear ordering < of each of these subsets Vi , such that each arc of H belongs to some Vi × Vi+1 ,
0 ≤ i ≤ k − 1, and u < w, z < v and uv, wz ∈ A(H) imply that uz ∈ A(H) for any u, w ∈ Vi ,
v, z ∈ Vi+1 , with all subscript addition modulo k. Theorem 4.1 can be extended to k-min orderings
as follows. A k-arc representation of a digraph H on a circle C with 2k special points (poles
N0 , N1 , . . . , Nk−1 , S0 , S1 , . . . , Sk−1 (in this clockwise order) consists of intervals Iv , Jv , v ∈ V (H)
consistent as before, now each Iv containing Si+1 , Si+2 , . . . , Sk−1 , N0 , N1 , . . . , Ni , for some 0 ≤ i ≤
k − 1, and no other poles, and each Jv containing Ni+1 , Ni+2 , . . . , Nk−1 , S0 , S1 , . . . , Si , for some
0 ≤ i ≤ k − 1, and no other poles, such that uv ∈ A(H) if and only if Iu and Jv are disjoint.
Theorem 11.1 A digraph H = (V, A) is a k-arc digraph if and only if it admits a k-min ordering.

In some cases when min orderings do not exist, there may still exist extended min orderings,
~ k the directed
which is sufficient for the polynomial solvability of LHOM(H) [25]. We denote by C
cycle on vertices 0, 1, . . . , k − 1. We shall assume in this section that H is weakly connected. This
~ k define the same
assumption allows us to conclude that any two homomorphisms `, `0 of H to C
−1
partition of V (H) into the sets Vi = ` (i), and we will refer to these sets without explicitly defining
~ k , and let Vi be the partition of V (H)
a homomorphism `. Thus suppose H is homomorphic to C
corresponding to all such homomorphisms.
~ k , and a 1-min ordering
Note that any H is homomorphic to the one-vertex digraph with a loop C
of H is just the usual min ordering. Also note that a min ordering of a digraph H becomes a k-min
~ k that H is homomorphic to. However, there are digraphs homomorphic to
ordering of H for any C
~ k which have a k-min ordering but do not have a min ordering - for instance C
~ k (with k > 1).
C
We observe for future reference that an unbalanced digraph H has only a limited range of possible
~ k , and hence a limited range of possible values of
values of k for which it could be homomorphic to C
k for which it could have a k-min orderings. It is easy to see that a cycle C admits a homomorphism
~ k only if the net length of C is divisible by k [24]. Thus any cycle of net length q > 0 in H
to C
limits the possible values of k to the divisors of q. If H is balanced, it is easy to see that H has a
k-min ordering for some k if and only if it has a min ordering.

30

~ k we shall consider the following version of the pair digraph.
For a digraph H homomorphic to C
(k)
The digraph H is the subgraph of H + induced by all ordered pairs (x, y) belonging to the same
set Vi . We say that (u, v) is a symmetrically k-invertible pair in H if H (k) contains a directed
walk joining (u, v) and (v, u). Thus a symmetrically k-invertible pair is a symmetrically invertible
pair in H in which u and v belong to the same set Vi . Note that H may contain symmetrically
invertible pairs, but no symmetrically k-invertible pair. Consider, for instance the directed hexagon
~ 6 . The pair 0, 3 is symmetrically invertible and symmetrically 3-invertible, but not symmetrically
C
6-invertible.
The extended version of our main theorem follows.
Theorem 11.2 The following statements are equivalent for a weakly connected digraph H.
1. H admits a k-min ordering
~ k and no component of H (k)
2. there exists a positive integer k such that H is homomorphic to C
contains a circuit
Proof: We shall in fact prove that the following statements are equivalent for a positive integer k
~k:
such that H is homomorphic to C
1. H admits a k-min ordering
2. no component of H (k) contains a circuit
Suppose H admits linear orderings < of sets Vi satisfying the Min property between consecutive
sets Vi , Vi+1 . Any circuit (x0 , x1 ), (x1 , x2 ), . . . , (xn , x0 ) in H (k) must have all vertices x0 , x1 , . . . , xn
in the same set Vi , and hence if all the pairs (xi , xi+1 ) were in the same component of H (k) we
would obtain the same contradiction with transitivity of < as above the statement of Theorem 4.2.
This proves that 1 implies 2.
~ k and no strong
Now we prove that 2 implies 1. Thus assume that H is homomorphic to C
(k)
component of H
contains a circuit. We shall construct a k-min ordering of H. We have again
the components of H (k) in dual pairs C, C 0 , where C 0 consists of the reverses of the pairs in C, and
we can proceed with a similar algorithm as before. At each stage of the algorithm, some component
of H (k) is chosen and its dual component discarded. We again choose a component X according to
the rules in Algorithm 1.
The proof of correctness is analogous to the proof of Propositions 9.4, 10.1.

We again note that the theorem implies a polynomial time algorithm to test whether an input
digraph H has a k-min min ordering. As noted above, it suffices to check for each component of
H separately, so we may assume that H is weakly connected. If H is balanced, we have already
observed this is only possible if H has a min ordering, which we can check in polynomial time.
Otherwise we find any unbalanced cycle in H, say, of net length q, and then test for circuits in
components H (k) for all k that divide q.

12 Conclusions
We have provided polynomial time algorithms, obstruction characterizations, and geometric representations, for digraphs admitting a min ordering, i.e., a CSL polymorphism. We believe they are a

31

useful generalization of interval graphs, encompassing adjusted interval digraphs, monotone proper
interval digraphs, complements of circular arcs of clique covering number two, two-dimensional ray
graphs, and other well known classes.
We have also similarly characterized digraphs admitting a CC polymorphism.
We now point out that the class of digraphs admitting a set polymorphism, i.e., CTS polymorphisms of all orders, coincides with the the class of digraphs with a min ordering, and so is equal
to the class of bi-arc digraphs.
Theorem 12.1 If there exists a circuit in a strong component of H + then either H + contains an invertible pair or there exists a closed walk W in H composed of walks W [v0 , v1 ], W [v1 , v2 ], ..., W [vr , v0 ]
with the following properties: each W [vi , vi+1 ] is constricted from below, has a positive net length r
and W [vi , vi+1 ] and W [vj , vj+1 ] avoid each other for every 0 ≤ i < j ≤ r (vr+1 = v0 )
Proof: Suppose C : (a0 , a1 ), (a1 , a2 ), . . . , (an , a0 ) is a circuit in a strong component S of H + .
Claim 12.2 We may assume that C is minimal and n > 1. Moreover S is an unbalanced component.
Proof: For contradiction suppose C is not minimal. Thus there is a minimal circuit which is
implied by S. Now by the properties shown in Section 7 for a minimal circuit when S is unbalance
then there is also a minimal circuit which all belong to the same strong component S.
If S is balanced then one can show there is a pair (x, y) on the lowest level of S where for each
pair in the circuit there exists a path constricted from below from (x, y) to that pair. This means
we can apply the Lemma 7.1 several times as necessary and conclude that there is a circuit on the
lowest level of S. Now we may assume that for every pair of the circuit there exists a path (with
net value zero and constricted from below) from (x, y) to that pair. But this is a contradiction
according to 8.5 as it would imply that there exists an invertible pair in a strong component of H + .

Suppose S is unbalanced and observe that by Theorem 7.2 we may assume that (bi , bi+1 ) =
(ai , ai+1 ), 0 ≤ i ≤ n, and (ai , ai+1 ) is extremal and all lie on one cycle (X, Y ) = Di in S. This
can be done because all the pairs lie on the same strong component S. We also assume that the
net value of such Di is minimum. We may assume that the net value of a directed path W from
(ai , ai+1 ) to (ai+1 , ai+2 ) is not zero. Otherwise W is constricted from below since (ai , ai+1 ) is an
extremal pair and hence W = (Ai , Bi ) where Ai and Bi avoid each other (part of Pi , Pi+1 ). Now
it is easy to see that there is a path from (ai , ai+1 ) to (ai , ai+2 ) (a walk from ai to a vertex with
the maximum height on Ai and then back to ai and a walk on Bi from ai+1 to ai+2 would give to
a path in H + from (ai , ai+1 ) to (ai , ai+2 )) and hence we get a shorter circuit.
Consider the walks Pi from Theorem 7.2 (2). Each walk Pi starts at ai and it is constricted and
has unbounded positive net length. Every Pi and Pj avoid each other. Moreover Pi is obtained by
walking around the closed walk X. Thus without loss of generality let the net value of portion of
Di from (a0 , a1 ) to (a1 , a2 ) has the smallest positive net value ` and let the net value of Di be m
where m is minimum. Note that (n + 1)` ≤ m.
Note that P0 and P1 avoid each other. Let X 0 be the closed walk starting at a0 corresponding
to P0 . Note that X 0 is also a closed walk starting at a1 corresponding to P1 .

32

Now consider the following walks : W0 = X 0 [a00 , a01 ], where a00 = a0 and a01 = a1 and Wj =
X 0 [a0j , a0j+1 ]; j = 1, 2, . . . where a0j+1 is a extremal vertex on X 0 and Wj has net length `. Observe
that Wi , Wi+1 , 1 ≤ i avoid each other since P0 , P1 avoid each other. Now at some point we must
have a0r = a0k . Without loss of generality we may assume that a00 = a0k . Note that r ≤ m because
X 0 has at most m extremal pairs. Note that the net value of Di is (r + 1)`.
Now (a00 , a01 ), (a01 , a02 ), . . . , (a0r , a00 ) is a circuit in S. We show that Wi and Wj avoid each other
for every 0 ≤ i < j ≤ r. Note that if there is a faithful arc from the q-th vertex of Wi−1 to the
−1
(q + 1)-th vertex of Wi+2
then we would have (a0i , a0i+1 )
(a0i+2 , a0i+1 ) (using the faithful arc at
index q) and because Wi , Wi+1 avoid each other and Wi+1 , Wi+2 avoid each other we conclude that
(a0i , a0i+1 ) and (a0i+2 , a0i+1 ) are both in S. On the other hand both (a0i , a0i+1 ), (a0i+1 , a0i+2 ) are in S and
hence (a0i+1 , a0i+2 ), (a0i+2 , a0i+1 ) are in S, a contradiction. Therefore for every i we have Wi , Wi+2
avoid each other. Now if r = 2 then we are done so we may assume that r ≥ 3.
Let d be the smallest integer such that Wj and Wj+d do not avoid each other (d ≥ 2). Note
without loss of generality we may assume that d ≤ r/2. Without loss of generality assume that
W0 , Wd do not avoid each other and d ≤ r/2. By considering the last faithful arc on W0−1 to
(a0d , a01 ) has net value ` and since Wd−1 , Wd avoid
Wd−1 we conclude that X1 : (a0d−1 , a0d )
each other and W0 , Wd−1 avoid each other, (a0d−1 , a0d ), (a0d , a01 ) are in S. We also note that us(a0d , a01 ) which is a directed walk of net
ing the faithful arc from W0−1 to Wd−1 we have (a00 , a01 )
(a00 , a01 )
(a01 , a02 ) has net value `. Now we have a circuit
value zero and hence X2 : (a0d , a01 )
0
0
0
0
0
0
0
0
(a1 , a2 ), (a2 , a2 ), . . . , (ad−1 , ad ), (ad , a1 ), and a closed walk that consists of a01 , a02 , . . . , a0d , a01 and has
net length (d − 1)` + ` + ` = (d + 1)` < (r + 1)`. This is a contradiction to the assumption about
the net value of Di .

Theorem 12.3 A digraph H admits a conservative CSL polymorphism if and only if it admits a
conservative set polymorphism.
Proof: Since a min ordering allows to define a conservative set polymorphism as the minimum, it
suffices to show that a digraph that does not have a min ordering also cannot have a conservative
set polymorphism. We show this by showing that a circuit in one component of H + means that H
does not have a conservative set polymorphism.
So suppose (a0 , a1 ), (a1 , a2 ), . . . , (an , a0 ) is a circuit in a strong component C of H + . By Theorem
12.1 either there exists an invertible pair and hence there is no CLS polymorphism or there exists
a closed walk W composed of walks W [v0 , v1 ], W [v1 , v2 ], ..., W [vr , v0 ] with the following properties:
Each W [vi , vi+1 ] is constricted from below, and has a positive net value r and W [vi , vi+1 ] and
W [vj , vj+1 ] avoid each other for every 0 ≤ i < j ≤ r (vr+1 = v0 ).
Now any conservative set function must assign f (v0 , v1 , . . . , vr ) = f (v1 , v2 , . . . , vr , v0 ) but since
the walks W [vi , vi+1 ], W [vj , vj+1 ], 0 ≤ i 6= r avoid each other, this is not possible.

We remark that in the proof we have only used the fact that H does not have a conservative
cyclic polymorphism. Thus we have actually proved that the class of bi-arc digraphs coincides with
each of the following classes of digraphs:
1. digraphs with conservative semi-lattice polymorphisms
2. digraphs with a conservative set polymorphism

33

3. digraphs with conservative cyclic polymorphisms of all arities.
Acknowledgement The authors are grateful to Benoit Larose for helpful comments and suggestions.

References
[1] G. Bagan, A. Durand, E. Filiot, and O. Gauwin. Efficient enumeration for conjunctive queries
over X-underbar structures, CSL’10 / EACSL’10)
[2] R.C. Brewster, T. Feder, P. Hell, J. Huang, and G. MacGillivray. Near-Unanimity Functions
and Varieties of Reflexive Graphs, SIAM J. Discrete Math. 22(3): 938-960 (2008)
[3] A. Bulatov, P. Jeavons, and A. A. Krokhin. Classifying the Complexity of Constraints Using
Finite Algebras, SIAM J. Comput. 34(3): 720-742 (2005)
[4] K.S. Booth and G.S. Lueker. Testing for the consecutive ones property, interval graphs, and
graph planarity using PQ-tree algorithms, Journal of Computer and System Sciences 13 (1976)
335 – 379.
[5] H. Chen, and B. Larose. Asking the metaquestions in constraint tractability, arXiv:1604.00932.
[6] D.G. Corneil, S. Olariu, and L. Stewart. The LBFS structure and recognition of interval graphs,
SIAM J. Discrete Math. 23 (2009) 1905–1953.
[7] C. Carvalho, L. Egri, M. Jackson, and Todd Niven. On Maltsev Digraphs, Electr. J. Comb.
22(1): P1.47 (2015)
[8] T. Feder and P. Hell. List homomorphisms to reflexive graphs, J. Combinatorial Theory B 72
(1998) 236–250.
[9] T. Feder, P. Hell, and J. Huang. List homomorphisms and circular arc graphs, Combinatorica
19 (1999) 487 – 505.
[10] T. Feder, P. Hell, and J. Huang. Bi-arc graphs and the complexity of list homomorphisms, J.
Graph Th. 42 (2003) 61– 80.
[11] T. Feder, P. Hell, J. Huang, and A. Rafiey. Adjusted interval digraphs, Electronic Notes in
Discrete Mathematics 32 (2009) 83–91.
[12] T. Feder, P. Hell, J. Huang, and A. Rafiey. Interval graphs, adjusted interval digraphs, and
reflexive list homomorphisms, Discrete Applied Mathematics 160 (2012) 697–707.
[13] T. Feder, P. Hell, B. Larose, C. Loten, M.H. Siggers, and C. Tardif. Graphs Admitting k-NU
Operations. Part 1: The Reflexive Case, SIAM J. Discrete Math, 27(4): 1940-1963 (2013)
[14] T.Feder and M.Vardi. Monotone monadic SNP and constraint satisfaction, In Proceedings of
STOC 1993, 612–622.

34

[15] T. Feder and M.Y. Vardi. The computational structure of monotone monadic SNP constraint
satisfaction: A study through Datalog and group theory, SIAM Journal on Computing, 28(1):
57–104 (1998).
[16] D.R. Fulkerson, and O.A. Gross. Incidence matrices and interval graphs, Pacific J. Math. 15
(1965) 835–855.
[17] M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York
(1980).
[18] M. Habib, R. McConnell, C. Paul, and L. Viennot. Lex-BFS and partition refinement, with
applications to transitive orientation, interval graph recognition and consecutive ones testing,
Theoretical Computer Science 234 (2000) 59–84.
[19] P. Hell, and J. Huang. Interval bigraphs and circular arc graphs, J. Graph Theory 46 (2004)
313–327.
[20] P. Hell, and J. Nešetřil. Colouring, constraint satisfaction, and complexity, Computer Science
Review 2(3): 143-163 (2008)
[21] R. Häggkvist, P. Hell, D. J. Miller, and V. Neumann Lara. On multiplicative graphs and the
product conjecture, Combinatorica 8 (1988) 71–81.
[22] A. Kazda. Maltsev digraphs have a majority polymorphism, Eur. J. Comb. 32(3): 390-397
(2011)
[23] P. Hell, M. Mastrolilli, M.M.Nevisi and A. Rafiey. Approximation of Minimum Cost Homomorphisms. ESA 2012: 587–598.
[24] P. Hell, and J. Nešetřil. Graphs and Homomorphisms. Oxford University Press, Oxford, 2004.
[25] P. Hell and A. Rafiey. The dichotomy of list homomorphisms for digraphs, SODA 2011.
[26] P. Hell and A. Rafiey. Monotone Proper Interval Digraphs, SIAM J. Discrete Math. 26(4)
(2012) 1576-1596.
[27] P. G. Jeavons. On the algebraic structure of combinatorial problems, Theoret. Comput. Sci.
200 (1998) 185–204.
[28] T. Jiang and D. B. West. Coloring of trees with minimum sum of colors, J. Graph Theory 32
(1999) 354–358.
[29] T. Jiang, and D.B. West. Coloring of trees with minimum sum of colors, J. Graph Theory 32
(1999) 354 – 358.
[30] C.G. Lekkerkerker, and J.C. Boland. Representation of a finite graph by a set of intervals on
the real line, Fundamenta Math. 51 (1962) 45–64.
[31] M. Maroti, and R. McKenzie. Existence theorems for weakly symmetric operations. Algebra
Universalis, 59 (2008), 463–489.

35

[32] I. Mustata, K. Nishikawa, A. Takaoka, S. Tayu, S. Ueno. On orthogonal ray tree, Discrete
Applied Mathematics 201: 201-212 (2016)
[33] C. Papadimitriou, K. Steiglitz. Combinatorial Optimization. Algorithms and Complexity,
Prentice-Hall 1982, ISBN 0-13-152462-3
[34] E. Prisner. A characterization of interval catch digraphs, Discrete Math. 73 (1989) 285–289.
[35] M. Sen, S. Das, A.B. Roy, and D.B. West. Interval digraphs: an analogue of interval graphs,
J. Graph Theory 13 (1989) 581–592.
[36] J. Spinrad. Efficient Graph Representations, Fields Institute Monographs, AMS 2003.
[37] X. Zhu. A simple proof of the multiplicativity of directed cycles of prime power length. Discrete
Appl. Math. 36 (1992) 333–345.

36

