Vol:.(1234567890)
Algorithmica (2021) 83:116–143
https://doi.org/10.1007/s00453-020-00751-1
1 3
Flip Distances Between Graph Orientations
OswinAichholzer, etal.[full author details at the end of the article]
Received: 25 June 2019 / Accepted: 15 July 2020 / Published online: 27 July 2020
© The Author(s) 2020
Abstract
Flip graphs are a ubiquitous class of graphs, which encode relations on a set of
combinatorial objects by elementary, local changes. Skeletons of associahedra, for
instance, are the graphs induced by quadrilateral flips in triangulations of a convex
polygon. For some definition of a flip graph, a natural computational problem to
consider is the flip distance: Given two objects, what is the minimum number of
flips needed to transform one into the other? We consider flip graphs on orienta-
tions of simple graphs, where flips consist of reversing the direction of some edges.
More precisely, we consider so-called
𝛼
-orientations of a graph G, in which every
vertex v has a specified outdegree
𝛼(
v
)
, and a flip consists of reversing all edges of a
directed cycle. We prove that deciding whether the flip distance between two
𝛼
-ori-
entations of a planar graph G is at most two is NP-complete. This also holds in the
special case of perfect matchings, where flips involve alternating cycles. This prob-
lem amounts to finding geodesics on the common base polytope of two partition
matroids, or, alternatively, on an alcoved polytope. It therefore provides an interest-
ing example of a flip distance question that is computationally intractable despite
having a natural interpretation as a geodesic on a nicely structured combinatorial
polytope. We also consider the dual question of the flip distance between graph
orientations in which every cycle has a specified number of forward edges, and a
flip is the reversal of all edges in a minimal directed cut. In general, the problem
remains hard. However, if we restrict to flips that only change sinks into sources, or
vice-versa, then the problem can be solved in polynomial time. Here we exploit the
fact that the flip graph is the cover graph of a distributive lattice. This generalizes a
recent result from Zhang etal. (Acta Math Sin Engl Ser 35(4):569–576, 2019).
Keywords Flip distance· α-Orientation· Graph orientation
An extended abstract of this paper appeared in the LNCS Proceedings of WG 2019. T. Huynh:
Supported by ERC Consolidator Grant 615640-ForEFront. K. Knauer: Affiliated with Laboratoire
d’Informatique et des Systèmes, Algorithmique, Combinatoire et Recherche Opèrationnelle,
Universitè Aix-Marseille. Supported by: ANR-16-CE40-0009-01, ANR-17-CE40-0015, ANR-
17-CE40-0018, RYC-2017-22701. T. Mütze: Also affiliated with Charles University, Faculty of
Mathematics and Physics, and supported by GACR Grant GA 19-08554S, and by DFG grant
413902284. B. Vogtenhuber: Partially supported by the Austrian Science Fund (FWF): I 3340-N35.
117
1 3
Algorithmica (2021) 83:116–143
1 Introduction
The term flip is commonly used in combinatorics to refer to an elementary, local,
reversible operation that transforms one combinatorial object into another. Such flip
operations naturally yield a flip graph, whose vertices are the considered combinato-
rial objects, and two of them are adjacent if they differ by a single flip. A classical
example is the flip graph of triangulations of a convex polygon [46, 57]; see Fig.1.
The vertex set of this graph are all triangulations of the polygon, and two triangula-
tions are adjacent if one can be obtained from the other by replacing the diagonal
of a quadrilateral formed by two triangles by the other diagonal. Similar flip graphs
have also been investigated for triangulations of general point sets in the plane [16],
triangulations of topological surfaces [41], and planar graphs [6, 10]. The flip dis-
tance between two combinatorial objects is the minimum number of flips needed to
transform one into the other. It is known that computing the flip distance between
two triangulations of a simple polygon [4] or of a point set [37] is NP-hard. The
latter is known to be fixed-parameter tractable [33]. On the other hand, the NP-hard-
ness of computing the flip distance between two triangulations of a convex polygon
is a well-known open question [12, 13, 17, 34, 38, 54]. Flip graphs involving other
geometric configurations have also been studied, such as flip graphs of non-crossing
perfect matchings of a point set in the plane, where flips are with respect to alternat-
ing 4-cycles [11], or alternating cycles of arbitrary length [29]. Other flip graphs
include the flip graph on plane spanning trees [2], the flip graph of non-crossing
partitions of a point set or dissections of a polygon [28], the mutation graph of sim-
ple pseudoline arrangements [53], the Eulerian tour graph of an Eulerian graph [59],
and many others. There is also a vast collection of interesting flip graphs for non-
geometric objects, such as bitstrings, permutations, combinations, and partitions
[22].
In essence, a flip graph provides the considered family of combinatorial objects
with an underlying structure that reveals interesting properties about the objects. It
can also be a useful tool for proving that a property holds for all objects, by proving
that one particularly nice object has the property, and that the property is preserved
Fig. 1 The flip graph of triangulations of a convex polygon
118
Algorithmica (2021) 83:116–143
1 3
under flips. Flip graphs are also an essential tool for solving fundamental algorith-
mic tasks such as random and exhaustive generation, see e.g. [3, 7, 50].
The focus of the present paper is on flip graphs for orientations of graphs sat-
isfying some constraints. First, we consider so-called
𝛼
-orientations, in which the
outdegree of every vertex is specified by a function
𝛼
, and the flip operation consists
of reversing the orientation of all edges in a directed cycle. We study the complexity
of computing the flip distance between two such orientations. An interesting special
case of
𝛼
-orientations corresponds to perfect matchings in bipartite graphs, where
flips involve alternating cycles. We also consider the dual notion of c-orientations,
in which the number of forward edges along each cycle is specified by a function c.
Here a flip consists of reversing all edges in a directed cut. We also analyze the com-
putational complexity of the flip distance problem in c-orientations.
There are several deep connections between flip graphs and polytopes. Spe-
cifically, many interesting flip graphs arise as the (1-)skeleton of a polytope. For
instance, flip graphs of triangulations of a convex polygon are skeletons of associa-
hedra [15], and flip graphs of regular triangulations of a point set in the plane are
skeletons of secondary polytopes (see [16, Chapter5]). Associahedra are general-
ized by quotientopes [48], whose skeletons yield flip graphs on rectangulations [14],
bitstrings, permutations, and other combinatorial objects. Moreover, flip graphs of
acyclic orientations or strongly connected orientations of a graph are skeletons of
graphical and co-graphical zonotopes, respectively(see [45, Sect.2]). Similarly, as
we show below, flip graphs on
𝛼
-orientations are skeletons of matroid intersection
polytopes. We also consider vertex flips in c-orientations, inducing flip graphs that
are distributive lattices and in particular subgraphs of skeletons of certain distribu-
tive polytopes. These polytopes specialize to flip polytopes of planar
𝛼
-orientations,
are generalized by the polytope of tensions of a digraph, and form part of the family
of alcoved polytopes(see [21]).
In the next section, we give the precise statements of the computational prob-
lems we consider, connections with previous work, and the statements of our main
results. In Sect.4, we give the proof of our first main result, showing that computing
the flip distance between
𝛼
-orientations and between perfect matchings is NP-hard
even for planar graphs. Section5 presents the proof of our second main result, where
we give a polynomial time algorithm to compute the vertex flip distance between
c-orientations. Finally, in Sect. 6 we show that computing the distance between
c-orientations, when double vertex flips are also allowed, is NP-hard.
2 Problems andMain Results
2.1 Flip Distance Between
˛
‑Orientations
Given a graph G and some
𝛼∶V(G)→ℕ0
, an
𝛼
-orientation of G is an orientation
of the edges of G in which every vertex v has outdegree
𝛼(v)
. An example for a
graph and two
𝛼
-orientations for this graph is given in Fig.2. A flip of a directed
cycle C in some
𝛼
-orientation X consists of the reversal of the orientation of all
edges of C, as shown in the figure. Edges with distinct orientations in two given
119
1 3
Algorithmica (2021) 83:116–143
𝛼
-orientations X and Y induce an Eulerian subdigraph of both X and Y. They can
therefore be partitioned into an edge-disjoint union of cycles in G which are
directed in both X and Y. Hence the reversal of each such cycle in X gives rise to
a flip sequence transforming X into Y and vice versa. We may thus define the flip
distance between two
𝛼
-orientations X and Y to be the minimum number of cycles
in a flip sequence transforming X into Y. We are interested in the computational
complexity of determining the flip distance between two given
𝛼
-orientations.
Problem1 Given a graph G, some
𝛼∶V(G)→ℕ0
, a pair X,Y of
𝛼
-orientations of
G and an integer
k≥0
, decide whether the flip distance between X and Y is at most
k.
The crucial difficulty of this problem is that a shortest flip sequence transform-
ing X into Y may flip edges that are oriented the same in X and Y an even number
of times, to reach Y with fewer flips compared to only flipping edges that are ori-
ented differently in X and Y; see the example in Fig.3. This motivates the follow-
ing variant of the previous problem:
1
1
1
1
1
1
2 2
12
1
1
1
1
1
1
2 2
12
Fig. 2 Two
𝛼
-orientations of a graph and a flip between them, where the values of
𝛼
are depicted on the
vertices
2 1
1
1
2 1
1
1
2 1
1
1
2 1
1
1
2 1
1
1
C1C2C3C4
D1
D2
D3
Fig. 3 An
𝛼
-orientation X of a graph. The
𝛼
-orientation Y obtained by flipping the four directed facial
cycles
C1,…,C4
can be reached with fewer flips by flipping only the three directed facial cycles
D1,D2,D3
in this order
120
Algorithmica (2021) 83:116–143
1 3
Problem2 Given
G,𝛼,X,Y,k
as in Problem1, decide whether the flip distance
between X and Y is at most k, where we only allow flipping edges that are oriented
differently in X and Y.
2.2 From
˛
‑Orientations toPerfect Matchings
The flexibility in choosing a function
𝛼
for a set of
𝛼
-orientations on a graph allows
us to capture numerous relevant combinatorial structures, some of which are listed
below:
• domino and lozenge tilings of a plane region [52, 58],
• planar spanning trees [26],
• (planar) bipartite perfect matchings [39],
• (planar) bipartite d-factors [18, 47],
• Schnyder woods of a planar triangulation [8],
• Eulerian orientations of a (planar) graph [18],
• k-fractional orientations of a planar graph with specified outdegrees[5],
• contact representations of planar graphs with homothetic triangles, rectangles,
and k-gons[19, 23, 24, 27].
In the following, we focus on perfect matchings of bipartite graphs. Consider any
bipartite graph G with bipartition
(V1,V2)
equipped with
With this definition, in each
𝛼
-orientation of G, the edges directed from
V1
to
V2
form a perfect matching. This is illustrated in Fig.4. Conversely, given a perfect
matching M of G, orienting all edges of M from
V1
to
V2
and all the other edges from
V2
to
V1
yields an
𝛼
-orientation of the above type. Furthermore, the directed cycles
in any
𝛼
-orientation of G correspond to the alternating cycles in the associated per-
fect matching. Flipping an alternating cycle in a perfect matching corresponds to
exchanging matching and non-matching edges. An example of the flip graph of
𝛼
∶V(G)→ℕ0,𝛼(x) ∶=
{
1 if x∈V1
,
d
G
(x)−1 if x∈V
2.
1
1
1
1
1
1
2 2
12
Fig. 4 An
𝛼
-orientation of a bipartite graph and the corresponding perfect matching
121
1 3
Algorithmica (2021) 83:116–143
perfect matchings of a graph is given in Fig.5. In this special case, Problem1 boils
down to:
Problem3 Given a bipartite graph G, a pair X,Y of perfect matchings in G and an
integer
k≥0
, decide whether the flip distance between X and Y is at most k.
The example from Fig.3 can be easily modified to show that when transform-
ing X into Y using the fewest number of flips, we may have to flip alternating cycles
that are not in the symmetric difference of X and Y; see the example in Fig.6. If we
Fig. 5 The flip graph of perfect matchings of a graph. The solid edges indicate flips along facial cycles,
and the dashed edges indicate flips along non-facial cycles
122
Algorithmica (2021) 83:116–143
1 3
restrict the flips to only use cycles in the symmetric difference of X and Y, then the
problem of finding the flip distance becomes trivial, as the symmetric difference is
a collection of disjoint cycles, and each of them has to be flipped, so Problem2 is
trivial for perfect matchings.
2.3 Flip Graphs andMatroid Intersection Polytopes
We proceed to give a geometric interpretation of the flip distance between
𝛼
-orienta-
tions as the distance in the skeleton of a 0/1-polytope.
Recall that a matroid is an abstract simplicial complex
(E,I)
, where
I⊆2E
satis-
fies the independent set augmentation property. The elements of
I
are called inde-
pendent sets. A base of the matroid is an inclusionwise maximal independent set.
It is well-known that perfect matchings in a bipartite graph
G=(V1∪V2,E)
are
common bases of two partition matroids
(E,I1)
and
(E,I2)
, in which a set of edges
is independent if no two share an endpoint in
V1
, or, respectively, in
V2
.
Similarly,
𝛼
-orientations can be defined as common bases of two partition
matroids. In this case, every edge of the graph G is replaced by a pair of parallel
arcs, one for each possible orientation of the edge. One matroid ensures that in a
basis, for every edge exactly one orientation is chosen. The second matroid encodes
the constraint that in a basis, each vertex v has exactly
𝛼(v)
outgoing arcs.
The common base polytope of two matroids is a 0/1-polytope obtained as the con-
vex hull of the characteristic vectors of the common bases. Adjacency of two ver-
tices of this polytope has been characterized by Frank and Tardos [25]. A shorter
proof was given by Iwata [30]. We briefly recall their result in the next theorem. To
state the theorem, consider a matroid
M=(E,I)
, a base
B∈I
, and a subset
F⊆E
.
The exchangeability graph G(B,F) of M is a bipartite graph with
B⧵F
and
F⧵B
as
vertex bipartition, and edge set
{ij ∣B⧵{i}∪{j}is a basis}
. This definition and the
theorem are illustrated in Fig.7 for the two partition matroids whose common bases
are perfect matchings of a graph.
Theorem1 ([25, 30]) For two matroids
M+=(E,I+)
and
M−=(E,I−)
, two com-
mon bases
A,B∈I+∩I−
are adjacent on the common base polytope if and only if
all the following conditions hold:
C1C2C3C4
D1
D2
D3
Fig. 6 A perfect matching X in a graph. The perfect matching Y obtained by flipping the four alternating
facial cycles
C1,…,C4
can be reached with fewer flips by flipping only the three alternating facial cycles
D1,D2,D3
in this order
123
1 3
Algorithmica (2021) 83:116–143
(i) the exchangeability graph G(A,B) of
M+
has a unique perfect matching
P+
,
(ii) the exchangeability graph G(B,A) of
M−
has a unique perfect matching
P−
,
(iii)
P+∪P−
is a single cycle.
From this theorem we can conclude that the flip graphs we consider on perfect
matchings and
𝛼
-orientations are precisely the skeletons of the corresponding poly-
topes of common bases.
It is interesting to compare Problems1 and3 with the analogous problems for
other families of matroid polytopes. For instance, it is known that for two bases A,B
of a matroid, the exchangeability graph G(A,B) has a perfect matching [9]. Hence
A can be transformed into B by performing
|AΔB|∕2
exchanges of elements (where
AΔB
is the symmetric difference of A and B), which is also the distance in the skel-
eton of the base polytope of the matroid. On the other hand, the problem of com-
puting the flip distance between two triangulations of a convex polygon amounts to
computing distances in skeletons of associahedra, which are known to be polyma-
troids (see [1] and references therein). This problem is neither known to be in ¶ nor
known to be NP-hard. Also note that for other families of combinatorial polytopes,
testing adjacency is already intractable. This is the case for instance for the polytope
of the Traveling Salesman Problem (TSP) [42], whose skeleton is known to have
diameter at most 4 [51]. On the other hand, the corresponding polytope is known to
be the common base polytope of three matroids.
Another important class of combinatorial polytopes are alcoved polytopes, see
[36]. It is known that the flip graphs of planar
𝛼
-orientations are skeletons of alcoved
polytopes, see [21]. Thus, by our results below, flip distances in this class are also
NP-hard to compute.
2.4 Hardness ofFlip Distance Between Perfect Matchings and
˛
‑Orientations
We prove that Problem3 is NP-complete, even for 2-connected bipartite subcubic
planar graphs and
k=2
. This clearly implies that Problem1 is NP-complete as well.
A={1,3,5,7,8}B={2,4,6,7,8}
3
1
65
4
2
A\
BB
\A
G(A, B)
G(B,A)
Fig. 7 Two common bases A and B (left and middle) of the matroids
M+
and
M−
, where
M+
and
M−
have
as independent sets all subsets of edges of the graph where no two share an endpoint in the set of circled
vertices, or the set of squared vertices, respectively. The right hand side shows the exchangeability graphs
G(A,B) of
M+
(solid edges) and G(B,A) of
M−
(dashed edges). As the conditions of Theorem1 are met,
the two bases are adjacent in the common base polytope, and adjacent in the flip graph shown in Fig.5
124
Algorithmica (2021) 83:116–143
1 3
Theorem2 Given a 2-connected bipartite subcubic planar graph G and a pair X,Y
of perfect matchings in G, deciding whether the flip distance between X and Y is at
most two is NP-complete.
As direct consequences of the proof of Theorem2 we get:
Corollary 1 Unless
𝖯=𝖭𝖯
, deciding whether the flip distance between two perfect
matchings is at most k is not fixed-parameter tractable with respect to parameter k.
Corollary 2 Unless
𝖯=𝖭𝖯
, the flip distance between two perfect matchings is not
approximable within a multiplicative factor
3∕2−𝜖
in polynomial time, for any
𝜖>0
.
We also prove that Problem2 is NP-complete, even for 4-regular graphs and
k=2
.
Theorem3 Given a 4-regular graph G and a pair X,Y of
𝛼
-orientations of G,
deciding whether the flip distance between X and Y is at most two is NP-complete.
Moreover, the problem remains NP-complete if we only allow flipping edges that are
oriented differently in X and Y
The proofs of Theorems2 and 3 are presented in Sect.4.
2.5 From
˛
‑Orientations inPlanar Graphs toc‑Orientations
In what follows, we generalize the problem, via planar duality, to flip distances in
so-called c-orientations.
Consider an arbitrary 2-connected plane graph G and its planar dual
G∗
. Then
for any orientation D of the edges of G, the directed dual
D∗
of D is obtained by
orienting any dual edge forward if it crosses a left-to-right arc in D in a simultane-
ous plane embedding of G and
G∗
, and backward otherwise; see Fig.8. Edge sets
of directed cycles in D correspond to edge sets of minimal directed cuts in
D∗
and
vice-versa. Hence D is acyclic (respectively, strongly connected) if and only if
D∗
is
strongly connected (respectively, acyclic). A directed vertex cut is a cut consisting
Fig. 8 Duality between flips in
𝛼
-orientations (solid edges) and in c-orientations (dashed edges)
125
1 3
Algorithmica (2021) 83:116–143
of all edges incident to a sink or a source vertex. Directed facial cycles in D are in
bijection with the directed vertex cuts in
D∗
, and vice versa. The unbounded face in
the plane embedding of D can be chosen such that it corresponds to a fixed vertex
⊤
in
D∗
.
Let D be an
𝛼
-orientation of G. Given a minimal cut in D separating
U⊆V(D)
from
U∶= V(D)⧵U
, we denote by
𝛿+(U)
the edges pointing from U to
U
in D. We
also let
d+
D
(v
)
denote the outdegree of vertex v in D. We have
which only depends on
𝛼
and G. Consequently, the set of orientations of
G∗
which
are directed duals of
𝛼
-orientations of G can be characterized by the property that
for every cycle C in
G∗
, the number of edges in clockwise direction is fixed by a
certain value c(C) independent of the orientation. The flip operation between
𝛼
-ori-
entations of D consists of the reversal of a directed cycle. In the corresponding set of
dual orientations of
D∗
, this translates to the reversal of the orientations of the edges
in a minimal directed cut, as shown on Fig.8.
The same notion has been investigated more generally without planarity condi-
tions under the name of c-orientations by Propp [47] and Knauer [31]. Given a graph
G, we can fix an arbitrary direction of traversal for each cycle C. Given a graph and
an assignment
c(C)∈ℕ0
to each cycle in G, one may define a c-orientation of G to
be an orientation having exactly c(C) edges in forward direction for every cycle C
in G. Note that it is sufficient to define the function c on a cycle basis of G, which
consists of no more than |E(G)| cycles. The flip operation on the set
Rc
of such c-ori-
entations of a graph is defined as the reversal of all edges in a minimal directed cut.
It is not difficult to see that flips make the set of c-orientations of a graph connected
(this will be noted in Sect.5).
From the duality between planar
𝛼
-orientations and planar c-orientations, deter-
mining flip distances between
𝛼
-orientations of 2-connected planar graphs reduces
to determining flip distances between the dual c-orientations. Note that planar duals
of bipartite graphs are exactly the Eulerian planar graphs. Theorem 2 therefore
directly yields:
Corollary 3 Given an Eulerian planar graph G and a pair X,Y of c-orientations of
G, deciding whether the flip distance between X and Y is at most two is NP-complete.
2.6 c‑Orientations andDistributive Lattices
A more local operation consists of flipping only directed vertex cuts, induced by
sources and sinks, excluding a fixed vertex
⊤
. We will refer to this special case as a
vertex flip. Specifically, given a pair of c-orientations X,Y of a graph G with a fixed
vertex
⊤
, we aim to transform X into Y using only vertex flips at vertices distinct
from
⊤
.
A c-orientation X of G might contain a cycle C in G which is directed in X.
According to the definition of a c-orientation, this means that C keeps the same
|
𝛿+(U)
|
=
∑
v∈U
d+
D(v)−
|
E(G[U])
|
=
∑
v∈U
𝛼(v)−
|
E(G[U])
|,
126
Algorithmica (2021) 83:116–143
1 3
orientation in every c-orientation of G. Consequently, any (minimal) directed cut in
a c-orientation of G is disjoint from E(C). Contracting the cycle C in G, we end up
with a smaller graph
G′
containing the same (minimal) directed cuts, such that the
c-orientations of G are determined by their corresponding orientations on
G′
. We
can therefore safely assume that the c-orientations that we consider are all acyclic.
Similarly, G will be assumed to be connected.
Problem4 Given a connected graph G with a fixed vertex
⊤
and a pair X,Y of acy-
clic c-orientations, what is the length of a shortest vertex flip sequence transforming
X into Y?
We should convince ourselves that under the assumptions made above, every pair
of c-orientations is reachable from each other by vertex flips. This property is pro-
vided in a much stronger way by a distributive lattice structure on the set
Rc
; see
Fig.9. The next theorem is a special case of Theorem 1 in Propp [47] where the
c-orientations are acyclic.
Theorem4 ([31, 47]) Let G be a graph with fixed vertex
⊤
and
Rc
a set of acyclic
c-orientations of G. Then the partial order
≤c
on
Rc
in which Y covers X if and only
if Y can be obtained from X by flipping a source defines a distributive lattice on
Rc
.
Hence Problem4 consists of finding shortest paths in the cover graph of a dis-
tributive lattice, where the size of the lattice can be exponential in the size of the
input G.
2.7 Every Distributive Lattice isaLattice ofc‑Orientations
We next point out that every distributive lattice is isomorphic to the distributive lat-
tice induced by a set of c-orientations of a graph. This relationship was described by
Knauer [32].
In order to represent a given distributive lattice L by an isomorphic lattice of
c-orientations, we need to construct a corresponding digraph D(L). For this purpose,
we shortly recall a classical result from lattice theory, Birkhoff’s Theorem (see [17]).
For any distributive lattice L,
J(L)
is the subposet of L induced by the set of join-
irreducible elements, these are the elements of L covering exactly one element.
On the other hand, given any poset P we may look at the distributive lattice
O(P)
formed by the downsets of P ordered by inclusion. Birkhoff’s Theorem in our setting
asserts that those two operations are inverse in the sense that
P≅J(O(P))
for any
finite poset P and
O(J(L)) ≅ L
for any finite distributive lattice.
The idea is to define a digraph D(L) whose vertex set consists of the elements of
J(L)
with an additional vertex
⊤
. The digraph is obtained from the natural upward-
orientation of
J(L)
plus additional arcs from all the sinks and sources to
⊤
. Let G(L)
be the underlying graph of D(L), and for every cycle C of G(L), fix c(C) to be the
number of forward-edges on c in the orientation D(L). Let
Dc
be the set of c-orien-
tations of G(L). Fix
⊤
as the unique non-flippable vertex. We now define
Lc(D(L))
127
1 3
Algorithmica (2021) 83:116–143
as the distributive lattice induced on
D
according to Theorem4. An example of this
construction is provided in Fig.10.
The following theorem is an easy consequence of Birkhoff’s Theorem.
Theorem5 ([32]) Let L be any distributive lattice and D(L) be the corresponding
digraph as defined above. Then
L≅Lc(D(L))
.
Theorem9 below gives a natural geometric embedding of the lattice L depend-
ing on the digraph D(L). This embedding is such that all values
zX(x)
are 0 or 1, and
Fig. 9 The distributive lattice induced by vertex flips in c-orientations. The reference orientation at the
bottom is the directed dual
D∗
of the orientation D of the graph G used in Figs.4 and 5, where some
parallel arcs incident with
⊤
are grouped together for simplicity. The numbers depicted at the vertices
indicate the number of times that each vertex is flipped with respect to the reference orientation
128
Algorithmica (2021) 83:116–143
1 3
the vectors
zX(.)
are exactly the characteristic vectors of the downsets of
J(L)
. The
convex hull of those vectors is known as the order polytope of
J(L)
[56], which is a
particular case of the above-mentioned alcoved polytopes. The problem of comput-
ing vertex flip distances between elements of L encoded by c-orientations of G(L)
therefore boils down to computing the distance between two downsets of
J(L)
in
their inclusion lattice, which is a simple special case of Problem4.
2.8 Facial Flips inPlanar Graphs
When we consider Problem4 on planar graphs, restricting to vertex flips and con-
sidering the dual plane graph amounts to considering only flips of directed facial
cycles, excluding the outer face whose dual vertex is
⊤
. We refer to these as facial
flips. Felsner [18] considered distributive lattices induced by facial flips. The follow-
ing computational problem is a special case of Problem4.
Problem5 Given a 2-connected plane graph G and a pair X,Y of strongly con-
nected
𝛼
-orientations, what is the length of a shortest facial flip sequence transform-
ing X into Y?
Zhang etal. [60] recently provided a closed formula for this flip distance, which
can be turned into a polynomial-time algorithm. We prove the analogous stronger
statement for Problem4.
Theorem6 There is an algorithm that, given a graph G with a fixed vertex
⊤
and
a pair X,Y of c-orientations of G, outputs a shortest vertex flip sequence between X
and Y, and runs in time
O(m3)
where m is the number of edges.
In the planar case, this directly translates to a polynomial-time algorithm for
Problem5. The proof of Theorem6 is presented in Sect.5. In [20], the distributive
lattice structure on c-orientations is generalized to so-called
Δ
-bonds, also known
Fig. 10 A distributive lattice
L represented by its Hasse
diagram (left), the correspond-
ing subposet of join-irreducible
elements
J(L)
(middle), and the
digraph D(L) associated with
the lattice (right)
LJ(L)D(L)
129
1 3
Algorithmica (2021) 83:116–143
as tensions. We believe that our proof of Theorem6 can be generalized to these
objects.
2.9 Flip Distance withLarger Cut Sets
While computing the cut flip distance between c-orientations is an NP-hard problem
in general (Theorem2), there is a polynomial-time-algorithm for computing the dis-
tance when only using vertex flips (Theorem6). It is natural to ask for a threshold
between the hard and easy cases of flip distance problems. Our hardness reduction
in Sect.4 involves very long directed cycles, which correspond to flips of directed
cuts in the dual c-orientations with cut sets of large size. Consequently, one may
hope that the problem gets easier when restricting the sizes of the cut sets involved
in a flip sequence. Our last result destroys this hope:
Theorem7 Let X,Y be c-orientations of a connected graph G with fixed vertex
⊤
.
It is NP-hard to determine the length of a shortest cut flip sequence transforming X
into Y, which consists only of minimal directed cuts with interiors of order at most
two.
We will present the proof of Theorem7 in Sect.6.
3 Preliminaries
In this section we recall some standard terminology concerning digraphs and posets
that will be used repeatedly in the paper.
3.1 Cuts andCut Sets
Given a directed graph D and a subset
U⊆V(D)
of vertices, we denote by
𝛿(U)
the set of all arcs in E(D) having one end in U and the other in
U∶= V(D)⧵U
. By
𝛿+(U)
, we denote the set of all arcs in E(D) directed from U to
U
. If
𝛿(U)=𝛿+(U)
,
we call
S=𝛿(U)
a directed cut or dicut induced by U, and U is referred to as a cut
set of S. In the case that D is weakly connected, the cut set is uniquely determined by
the dicut.
3.2 Posets andLattices
A partially ordered set, or poset for short, is a pair
(P,≺)
, where P is a set and
≺
is
a reflexive, antisymmetric and transitive binary relation on P. Posets can be rep-
resented more compactly by their minimal comparabilities: We say that
x≺y
is a
cover relation, or y covers x, if there is no z in the poset with
x≺z≺y
. This defines
the cover graph of P, which has the elements of P as vertices, and an edge for every
cover relation. The Hasse diagram of P is a drawing of the cover graph in the plane,
130
Algorithmica (2021) 83:116–143
1 3
where vertices are represented by distinct points and for every cover relation
x≺y
,
the edge between x and y is drawn as a straight line going upwards from x to y.
The downset of an element y in P is the set of all x with
x≺y
. A poset P is called
a lattice, if for any two elements x and y in P there is a unique smallest element z
such that
x≺z
and
y≺z
, and a unique largest element z such that
z≺x
and
z≺y
.
These elements are called the join and the meet of x and y, respectively. A lattice is
called distributive, if the join and meet operations distribute over each other.
4 Flip Distance Between Perfect Matchings andBetween
˛
‑Orientations
The proof of Theorem2 is by reduction from the following NP-complete problem.
Theorem8 (Plesńik [44]) Deciding directed Hamiltonicity of orientations of cubic
planar graphs is NP-complete.
The above problem remains NP-complete if we additionally assume 2-connectiv-
ity of the cubic graph and that the orientation does not have sinks or sources (other-
wise, there is no directed Hamiltonian cycle).
Proof ofTheorem2 As each flip sequence of length at most two can be used as a
polynomially verifiable certificate, the problem is clearly in NP.
We now provide a reduction of the decision problem in Theorem8 to Problem3.
So suppose we are given an orientation D of a 2-connected cubic planar graph with-
out sinks and sources, and assume without loss of generality that
|V(D)|≥3
. Given
D, we define an undirected graph
G=G(D)
as follows; see Fig.11: For each vertex
v∈V(D)
we create a vertex
xv
in G, and for each arc
e∈E(D)
we create a pair of
vertices
x+
e
,x
−
e
in G. The edges of G are defined as follows: For each arc
e∈E(D)
,
we connect x
+
e
and
x
−
e
with an edge in G. Furthermore, we denote by
V1
and
V2
the
vertices of D with outdegree 1 or 2, respectively. For each
v∈V1
, if
e,f∈E(D)
are
the two incoming arcs at v and g is the outgoing arc, then we add the edges x
+
e
x
v
,
x+
f
x
v
,
x+
e
x
−
g
, and x
+
f
x
−
g to G. Similarly, for each
v∈V2
, if
e,f∈E(D)
are the two out-
going arcs at v and g is the incoming arc, then we add the edges
x
−
e
xv
,
x−
fxv
,
x−
ex+
g
,
and
x−
fx+
g
to G. We refer to the 4-cycles in G formed by these edges as
C4
-gadgets.
Note that G is subcubic, planar, 2-connected, and bipartite. Specifically, the biparti-
tion is given by
{xv∣v∈V1}∪{x−
e∣e∈E(D)}
and
{
x
v∣
v
∈
V
2}∪{
x
+
e∣
e
∈
E
(
D
)}
.
We construct a pair of perfect matchings X,Y on G as follows. The first matching
X is defined by fixing a particular perfect matching on each
C4
-gadget, and the sec-
ond matching Y is obtained from X by flipping all cycles formed by the
C4
-gadgets;
see Fig.11. We claim that X and Y have flip distance at most two in G if and only if
D has a directed Hamiltonian cycle. From this the theorem follows.
First, assume there is a directed Hamiltonian cycle H in D. We define a pair of
cycles
C1,C2
in G, where
C1
and
C2
both contain all the edges
{
x
+
e
x
−
e∣
e
∈
E
(
H
)}
,
131
1 3
Algorithmica (2021) 83:116–143
plus additional edges defined as follows. For each vertex
v∈V(D)
, consider the cor-
responding
C4
-gadget in G with the two incident edges corresponding to the edges
incident with v on H. The endpoints of those edges on the gadget divide it into two
alternating paths in X, one with matching edges at both ends and one with non-
matching edges at both ends. We add the edges on those two types of paths to
C1
or
C2
, respectively. Note that
C1
is an alternating cycle in X. Moreover, after flipping
C1
,
the cycle
C2
is alternating, and flipping
C2
yields Y, as each edge in a
C4
-gadget gets
flipped once while the remaining edges are flipped an even number of times and thus
remain unchanged.
For the reverse implication, assume that X and Y are transformable into each
other by flipping at most two alternating cycles. As the symmetric difference
XΔY
contains at least three disjoint cycles (recall the assumption
|V(D)|≥3
), exactly
two cycles
C1,C2
are flipped to transform X into Y, and neither
C1
nor
C2
is one
of the 4-cycles formed by the
C4
-gadgets. As the edges outside the gadgets remain
unchanged, they are covered by both
C1,C2
or by neither of them. We claim that
H∶= {e∈E(D)∣x+
ex−
e∈E(C1)}
is the arc set of a directed Hamiltonian cycle in D.
Since up to isomorphism, H is obtained from
E(C1)
by contraction of the
C4
-gadg-
ets, H forms a cycle in D (here we need that D is cubic). If the cycle H is not a
v∈V1
ef
g
v∈V2
ef
g
x+
ex+
f
x+
g
x−
ex−
f
x−
g
xv
x+
ex+
f
x+
g
xv
x−
ex−
f
x−
g
Fig. 11
C4
-gadgets to construct the undirected graph
G=G(D)
(right) from the digraph D (left) in the
proof of Theorem2. The edges of the matchings X and Y in G are indicated by bold solid and dashed
lines, respectively
132
Algorithmica (2021) 83:116–143
1 3
directed cycle in D, there would be some
v∈V1
with two incoming incident edges
from H. However, in this case, the path in the corresponding
C4
-gadget contained in
C1
consists of two edges, one of which is not in X, contradicting that
C1
is an alter-
nating cycle in X. Finally, the directed cycle H has to be spanning. Indeed, if there
is a
C4
-gadget not traversed by
C1
, then
C2
would be equal to the 4-cycle in the cor-
responding gadget, a contradiction.
◻
Proof ofTheorem3 We use the following hardness result of Peroche [43]. Given a
digraph D, where each vertex has indegree and outdegree equal to 2, it is NP-com-
plete to decide if E(D) is the union of two directed Hamiltonian cycles. Given such a
digraph D, let
� �
D
be the digraph obtained from D by reversing the direction of every
arc. We regard D and
� �
D
as
𝛼
-orientations X and Y of the same underlying graph G,
where
𝛼(v)=2
for all
v∈V(G)
. The theorem follows by observing that the flip dis-
tance between X and Y is at most 2 if and only if E(D) is the union of two directed
Hamiltonian cycles. Moreover, the same statement holds when we only allow flip-
ping edges that are oriented differently in X and Y.
◻
5 Vertex Flip Distance Between c‑Orientations
In this section we prove Theorem6.
Recall that, given a graph G with a fixed vertex
⊤
, we only allow vertex flips at
vertices distinct from
⊤
. In the case that G is connected, we distinguish between
two types of dicuts as follows: we say that a dicut S in an orientation of G is posi-
tive with respect to
⊤
if and only if the uniquely determined cut set U of S does not
contain
⊤
. Otherwise the dicut is called negative. We also define the interior of S,
denoted
Int (S)
, as the cut set U of S if S is positive and as its complement
U
if S is
negative. That is,
Int (S)
is the set of vertices on the side of the cut opposite to
⊤
.
The following lemma is needed to decompose the edges of certain digraphs into
dicuts with nested cut sets. Formally, for a digraph D and dicuts
S1=𝛿(U1)
and
S2=𝛿(U2)
, the pair
S1,S2
is called laminar if either
U1⊆U2
,
U2⊆U1
,
U1∩U2=�
,
or
U1∪U2=V(D)
; see Fig.12. A family of dicuts in D is called laminar if all of
its pairs are laminar. A balanced digraph is a digraph in which every cycle of the
underlying graph has the same number of forward and backward edges.
Lemma 1 Let D be a balanced digraph. Then E(D) can be decomposed into a lami-
nar family of disjoint minimal dicuts.
Proof We prove the statement by induction on |E(D)|. It is clearly true if
E(D)=�
.
Assume for the induction step that
|E(D)|=k≥1
and the statement holds for all
digraphs with less than k arcs.
As D is balanced, it is obviously acyclic and therefore contains a source
s∈V(D)
. Each cycle in the underlying graph of D that contains s has exactly one
forward and one backward edge incident to s. Therefore, the digraph
D′
obtained
from D by contracting the set
𝛿+({s})
of arcs incident to s is still balanced and has
133
1 3
Algorithmica (2021) 83:116–143
less than k edges. By the induction hypothesis, there exists a laminar decomposition
of
E(D�)=E(D)⧵𝛿+({s})
into disjoint dicuts in
D′
and thus in D. Note that the
dicuts in
D′
are exactly those of D disjoint from
𝛿+({s})
, and laminarity is preserved.
Hence adding a decomposition of the directed vertex cut
𝛿+({s})
into minimal dicuts
to the collection gives rise to a decomposition of E(D) into disjoint minimal dicuts.
This resulting decomposition is also laminar. To see this, let
V1,…,Vl
denote the
vertex sets of the weak components of
D−s
(
l=1
is possible). The new minimal
cuts added to the decomposition are induced by the cut sets
Ui∶= V(D)⧵Vi
for
i∈[l]
. We clearly have
Ui∪Uj=V(D)
for
i≠j∈[l]
. Moreover, for any minimal
dicut S in the laminar decomposition of
D′
, the cut set corresponding to S in D fully
contains
Ui
or is disjoint from
Ui
for some
i∈[l]
(otherwise S would not be mini-
mal). This finally implies that each pair of cuts in the new decomposition is laminar,
as desired.
◻
For every pair X,Y of c-orientations on a graph G, the difference X
⧵
Y denotes
the set of arcs in X whose orientation is reversed in Y. Because X and Y are c-orien-
tations, every cycle in G has the same number of forward- and backward-edges in
X⧵Y
. The digraph
trans(X,Y)
obtained from X by contracting X
⧵
Y therefore forms
a balanced digraph. Consequently, Lemma1 provides another proof that c-orienta-
tions can be reached from one another by flipping minimal dicuts.
We now consider the partial order defined on acyclic c-orientations of an
n-vertex graph such that the covering relation corresponds to flipping a source
vertex. Recall that by Theorem4, this partial order is a distributive lattice. We
now reuse a result from Propp [47] and Felsner and Knauer [20] that gives an
embedding of this distributive lattice into
ℕn−1
, which led to the introduction of
X\Y
S1
S2
S3
S4
S5S6
S7
S=S(X, Y)
={S1,S
2,...,S7}
−1
−20
+1 −1
0
+1
P
S1
S2S3
S7
S4
S5
S
6
Fig. 12 A laminar collection
S
of disjoint minimal dicuts of
X⧵Y
(left), where the positive ones are
dashed, and the negative ones are dotted, and the corresponding poset P of dicuts in
S
ordered by inclu-
sion (right) with its associated signed weights
sgn (S)
⋅
w(S)
,
S∈S
134
Algorithmica (2021) 83:116–143
1 3
distributive polytopes by Felsner and Knauer [21]. This theorem is illustrated in
Fig.8, where the values of the functions
zX
are depicted in the vertices of the
graph G.
Theorem9 ([20, 47]) Let G be a graph on n vertices with a fixed vertex
⊤
, X an
acyclic c-orientation of G, and denote by
Xmin
the minimal element of the associ-
ated distributive lattice. Then the number of times
zX(x)
a vertex
x∈V(G)⧵{⊤}
is flipped in an upward lattice path from
Xmin
to X is independent of the sequence.
The resulting function
zX∶
R
c
→ℕ
n−1
is a lattice embedding. That is, for every
x,y∈
ℕ
n−1
corresponding to c-orientations of G, the join and meet correspond to
min(x,y)
and
max(x,y)
, respectively.
In other words, the distributive lattice on
Rc
is isomorphic to an induced sublat-
tice of the componentwise dominance order on
ℕn−1
. We call a vertex flip sequence
monotone if every flipped vertex is either only flipped as a source or only as a sink.
With this definition, Theorem9 yields the following:
Corollary 4 Let G be a graph with fixed vertex
⊤
and X,Y a pair of acyclic c-orien-
tations on G. Then every monotone vertex flip sequence transforming X into Y has
minimal length.
Consider two c-orientations X,Y of G. Our goal is to construct a monotone flip
sequence from X to Y. By Lemma1, there is a laminar decomposition of the edges in
trans(X,Y)
into minimal dicuts. The latter also form a laminar collection
S=S(X,Y)
of minimal dicuts in X which partition
X⧵Y
. Therefore reversing these dicuts yields
Y.
We construct a poset P on
S
by the inclusion order of the interiors of the
minimal dicuts. That is, for
S,T∈S
, S is ordered before T in P if and only if
Int (S)⊆Int (T)
; see Fig. 12. Since
S
is laminar, the cover graph of P is a for-
est, with the additional property that every non-maximal element S is covered by
a unique other element, which we denote by
cov (S)
. Moreover, for each vertex
x∈V(G)
in the interior of at least one of the cuts in
S
, we let
Sx
be the (unique)
minimal element of the poset P such that
x∈Int (Sx)
. Also, for each
S∈S
we
denote by
Int (S) ∶= {x∈V(G)∣Sx=S}⊆Int (S)
the set of vertices in the interior
of S but in none of the interiors of the cuts covered by S in the poset.
For each dicut
S∈S
we define an integer weight w(S) and a sign
sgn (S) ∈ {+,0,−}
as follows; see Fig.12. If
S∈S
is a maximal element in P then
we define
w(S) ∶= 1
, and
sgn (S) ∶= +
if S is positive and
sgn (S) ∶= −
otherwise.
For every sign
s∈ {+, 0, −}
and dicut
S∈S
, we say that S agrees with s, if either
s=0
, or if
s=+
and S is positive, or
s=−
and S is negative. For every non-maxi-
mal
S∈S
, we inductively define
and
w
(S) ∶=
{
w(cov (S)) + 1 if Sagrees with sgn (cov (S))
,
w(cov (S)) − 1 otherwise,
135
1 3
Algorithmica (2021) 83:116–143
It follows from this definition that the weights are non-negative and that
sgn (S)=0
if and only if
w(S)=0
for every
S∈S
. We will see that given a
minimal dicut S in
S
, the weight w(S) describes the number of times each ver-
tex which lies in
Int (S)
will be flipped, whereas
sgn (S)
captures the direction in
which (all) these vertices are flipped. That is, a positive sign means that vertices
are flipped from sources to sinks, while a negative sign means that vertices are
flipped from sinks to sources. We will need the following auxiliary statement.
Lemma 2 Let X,Y be acyclic c-orientations of a connected graph G with fixed ver-
tex
⊤
. If
S=X⧵Y
is a positive dicut, then there is a vertex flip sequence transform-
ing X into Y such that only vertices in
Int (S)
are flipped, each exactly once from
source to sink.
The analogous statement for negative dicuts holds with sources and sinks
exchanged.
Proof We prove the statement by induction on
|Int (S)|
. If
Int (S)
is a single vertex,
then S corresponds to the arcs incident to a source, and the statement holds.
For the induction step assume
|Int (S)|=k≥2
and that the claim holds for all
positive cuts in c-orientations of G whose interiors have order less than k. Since
X is acyclic, the induced subdigraph
X[Int (S)]
is also acyclic and thus contains a
source
x∈Int (S)
. Since
Int (S)
is the cut set of S, x is a source in X as well. Let
Z be the c-orientation obtained from X by a vertex flip at x. It follows that the cut
𝛿(Int (S)⧵{x})
in Z is positive with interior of order
k−1
. By induction, there is a
vertex flip sequence from Z to Y such that only vertices in
Int (S)⧵{x}
are flipped,
each exactly once from source to sink. Starting with a vertex flip at x and continu-
ing with this flip sequence yields a flip sequence from X via Z to Y with the desired
properties.
◻
We are now in position to prove the main result of this section.
Theorem10 Let X,Y be acyclic c-orientations of a connected graph G. There is
a monotone vertex flip sequence transforming X into Y which can be computed in
cubic time in |E(G)|.
Proof Consider the following strengthening of the theorem:
Claim Let X,Y be acyclic c-orientations of a connected graph G and
S=S(X,Y)
a laminar decomposition of
X⧵Y
into disjoint minimal dicuts. Then there is a mono-
tone vertex flip sequence from X to Y, such that every flipped vertex x is contained
sgn
(S) ∶=
⎧
⎪
⎨
⎪
⎩
sgn (cov (S)) if sgn (cov (S)) ≠0 and w(S)≠0,
+if sgn (cov (S)) = 0, w(S)≠0 and Sis positive,
−if sgn (cov (S)) = 0, w(S)≠0 and S
is negative,
0 if w(S)=0.
136
Algorithmica (2021) 83:116–143
1 3
in the interior of the dicut
Sx∈S
, and x is flipped
w(Sx)
times from source to sink if
sgn (Sx)=+
, and from sink to source otherwise.
We prove this claim by induction on the size of
S
. The statement is clearly true if
X=Y
(which means that
|S|=0
), settling the base case of the induction. Assume
for the induction step that we are given a pair
X≠Y
of c-orientations and a laminar
decomposition
S
of
X⧵Y
of size
k≥1
. Assume that the claim holds for all pairs of
c-orientations with a laminar decomposition of size less than k.
In the poset P on
S
we consider a minimal element corresponding to a cut
S∈S
,
i.e., we have
Int (S)= Int (S)
and all vertices
x∈Int (S)
satisfy
Sx=S
. Lemma2
gives a vertex flip sequence
F1
that flips only vertices in
Int (S)
, each exactly once
from source to sink if S is positive and from sink to source if S is negative. Applying
this flip sequence to X, we obtain an intermediate c-orientation Z that differs from
X only by the reversal of all edges in S. Consequently,
S⧵{S}
is a laminar decom-
position of
Z⧵Y
into minimal dicuts in Z of size
k−1
. By induction, we also have
a vertex flip sequence
F2
transforming Z into Y with the aforementioned properties.
Note that the weights and signs of all dicuts
T∈S⧵{S}
defined with respect to
S
or
S⧵{S}
are the same, so we may simply write w(T) and
sgn (T)
. Furthermore, the
set
Int (T)
defined with respect to
S
is a subset of the same set defined with respect
to
S⧵{S}
. To complete the induction step, we distinguish two cases.
The first case is that S is a maximal element in P, or that S agrees with
sgn (cov (S))
. In this case, we claim that the concatenation F of
F1
and
F2
is a flip
sequence transforming X via Z into Y with the desired properties. It suffices to check
this for the vertices in
Int (S)= Int (S)
, since for all other vertices, the claimed prop-
erties follow inductively (they are never flipped in
F1
, so their behavior in F will be
the same as in
F2
). If S is a maximal element in P, then
w(S)=1
and every vertex
x∈Int (S)
will be flipped exactly once. Moreover, according to Lemma2, if S is
positive, i.e.,
sgn (S)=+
, then x is flipped from source to sink, and if S is negative
and
sgn (S)=−
, then x is flipped sink to source. It remains to consider the subcase
that S is not maximal, i.e.,
cov (S)
exists. Consider any vertex
x∈Int (S)
. During
the flip sequence F, the vertex x is flipped once in
F1
and
w(cov (S))
times in
F2
,
so
w(S)=w(cov (S)) + 1
times in total, as required. Moreover, the assumption that
S agrees with
sgn (cov (S))
means that either
sgn (cov (S)) = +
and S is positive or
sgn (cov (S)) = −
and S is negative, or
w(cov (S)) = sgn (cov (S)) = 0
. We conclude
from the inductive assumption that in those three cases, x is only flipped from source
to sink in both
F1
and
F2
, or only sink to source in both, or only once in
F1
but not in
F2
, respectively. Consequently, x satisfies the inductive claim in all cases.
The second case is that S is not maximal, i.e.,
cov (S)
exists, and that S does not
agree with
sgn (cov (S))
. This means that
w(S)=w(cov (S)) − 1
. Without loss of
generality, assume that S is positive and consequently
sgn (cov (S)) = −
(the other
case is symmetric). Consider again the vertex flip sequence F obtained by concat-
enating
F1
and
F2
. This flip sequence would transform X via Z into Y, however, we
will not actually apply F, but modify the sequence as follows. By Lemma2,
F1
flips
each vertex in
Int (S)
exactly once from source to sink. By induction, in
F2
, each
vertex in
Int (S)
contained in the interior of
cov (S)
(defined with respect to
S⧵{S}
)
is flipped from sink to source. Let x be the last element of
F1
and consider the sub-
sequence
x,x1,…,xk,x
of F starting with x and ending with the first occurrence of
137
1 3
Algorithmica (2021) 83:116–143
x in
F2
. None of the vertices
x1,…,xk
is adjacent to x in G, because after the first
vertex flip at x (from source to sink) all edges incident with x are incoming, and in
F2
we only flip sinks to sources. This shows that deleting the first two occurrences
of x from F preserves the number of and direction of all flips at vertices distinct
from x, and still transforms X into Y. Repeated application of this argument pro-
duces a reduced vertex flip sequence
F′
transforming X into Y such that each vertex
x∈V(G)⧵Int (S)
is flipped the same number of times and in the same direction
as in
F2
. By the inductive assumption, this means that x is flipped
w(Sx)
times from
source to sink if
sgn (Sx)=+
, and
w(Sx)
times from sink to source if
sgn (Sx)=−
.
On the other hand, every
x∈Int (S)
is missing its first occurrence in
F2
but is flipped
in the same way from sink to source for all remaining occurrences. This implies
that x is flipped
w(S)=w(cov (S)) − 1
times from sink to source, as it should. This
proves that
F′
is a vertex flip sequence from X to Y satisfying the conditions in our
claim, completing its proof.
It remains to verify that the recursive algorithm obtained from this inductive
argument runs in cubic time in
m∶= |E(G)|
. First of all, the number of dicuts in
any laminar decomposition, which corresponds to the number of induction steps, is
bounded by the number of edges m. Consequently, it suffices to bound the number
of operations needed in one induction step in terms of m. Specifically, we need to
compute the cover relations of P, the weights and signs of the dicuts, find a mini-
mal element of the poset P, test its properties for the case distinction and construct
the resulting flip sequence by concatenation and possibly deletion of double occur-
rences, all of which can be done in time
O(m2)
. This proves an upper bound of
O(m3)
for the total number of steps performed for the construction of the monotone
flip sequence to transform X into Y. Finally, a laminar decomposition
S
of
X⧵Y
as
guaranteed by Lemma1 can be computed in time
O(m3)
as well, by following the
recursive strategy explained in the proof of the lemma. This completes the proof.
◻
Combining Corollary4 and Theorem10 yields Theorem6.
6 Flip Distance withLarger Cut Sets
In this section we prove Theorem7 by reduction from the following NP-hard
problem.
Given a (finite) poset
(P,≺)
, its height is the maximum size k of a chain
x1≺x2≺
⋯
≺xk
in P. A linear extension of P is a sequence
(x1,…,xn)
of all
elements of P such that
xi≺xj
implies that
i<j
. Given a linear extension
L=(x1,…,xn)
of P, a jump is a pair
xi,xi+1
in L for which
xi⊀xi+1
in P. Con-
versely, a bump is a pair
xi,xi+1
such that
xi≺xi+1
. The jump number s(P) of P is
the minimum number of jumps among all linear extensions of P. The Jump Num-
ber Problem is the algorithmic problem of computing the jump number of a poset
given by its comparabilities.
138
Algorithmica (2021) 83:116–143
1 3
Theorem11 ([40, 49]) Determining the jump number of a poset of height two is
NP-hard.
Proof ofTheorem7 We provide a Turing-reduction of the Jump Number Problem
for posets of height two to the problem stated in the theorem. For this purpose,
assume we are given a poset
(P,≺)
of height two with bipartite Hasse diagram
G=(P1∪P2,E)
as an instance for the Jump Number Problem. We may assume that
P has no isolated elements and that
P1
contains all minimal elements and
P2
all max-
imal elements of the poset. We construct an auxiliary graph
G′
from G by adding an
additional unique maximal element
⊤
, and connecting it with edges to all vertices of
G. We construct two orientations X,Y of
G′
as follows: In both orientations all edges
are oriented from
P1
to
P2
. Moreover, in X all edges incident with
⊤
are oriented
towards
⊤
, while in Y all these edges are oriented away from
⊤
. As X,Y are obtained
from each other by flipping all edges incident with
⊤
(this flip is not allowed, though,
as
⊤
is the fixed vertex), they are c-orientations with respect to the samec.
Let d denote the minimal flip distance between these c-orientations accord-
ing to the conditions of the theorem. We will complete the proof by showing that
s(P)=d−1
.
We first show that
s(P)≥d−1
. For this argument, let
L=(x1,…,xn)
be an arbi-
trary linear extension of P. As P has height two, the elements
{x1,…,xn}
of P are
partitioned into subsets
B1,…,Bm
of size one or two, such that for all
Bi,Bj
with
i<j
, the elements from
Bi
appear before the elements from
Bj
in L, and such that the
two-element sets
Bi
contain exactly all bump pairs. We define a flip sequence that
starts with the orientation X and consecutively flips the cuts induced by
B1,…Bm
.
Since for all
1≤i≤m
, each of
Bi
and
Bi
∶= (P∪{⊤}) ⧵B
i
induces a connected
subgraph of
G′
, these are indeed minimal cuts. Moreover, each of these cuts is flip-
pable. This is obviously true for
B1
, as
B1
induces a dicut in X. Now assume induc-
tively that the cuts induced by
B1,…,Bk−1
for some
k≥2
have been flipped. As L is
a linear extension of P, all elements in the downset of
Bk
in P but not in
Bk
are in one
of the
Bi
with
i<k
. This implies that every arc between some
x∈Bk
and
y∉Bk
is
oriented from x to y in the current orientation, and thus
Bi
is indeed flippable.
In this flip sequence, every arc in X not incident to
⊤
will be flipped zero or two
times and thus maintains its original orientation, while all the edges incident to
⊤
get
reversed, as they are incident to exactly one set
Bi
. Consequently, the flip sequence
transforms X into Y, proving that
d≤m
. As m equals the number of jumps in L plus
1 (every non-jump is a bump within one of the
Bi
), this yields
d−1≤s(P)
.
We now show that
s(P)≤d−1
. Assume that
B1,…,Bd⊆P
are the cut sets of
size one or two appearing (in this order) in a shortest flip sequence transforming X
into Y. We may assume that among all shortest flip sequences, this sequence also
minimizes
|B1|+|B2|+…+|Bd|
. Since each vertex
x∈P
has an outgoing arc to
⊤
in X which must be reversed during the flip sequence, x must be contained in at
least one of the
Bi
. We claim that x is contained in at most one of the
Bi
. That is, the
Bi
are pairwise disjoint. Assume to the contrary that
x∈Bi∩Bj
for some
i<j
and
that
Bi,Bj
is the only intersecting pair among
Bi,Bi+1,…,Bj
(by minimizing
j−i
).
In particular, none of the cut sets
Bi+1,…,Bj−1
contains x, and x is the only ver-
tex flipped multiple times in this subsequence. We are then in one of the four cases
139
1 3
Algorithmica (2021) 83:116–143
Bi=Bj={x}
, or
Bi={x,y}
and
Bj={x}
, or
Bi={x}
and
Bj={x,z}
, or
Bi={x,y}
and
Bj={x,z}
for some elements
y,z∈P
distinct from x. Since no vertex adjacent
to x in
G′
can be flipped by
Bi+1,…,Bj−1
, it follows that in each of these cases, the
sequence
is a valid flip sequence from X to Y of length at most d and with decreased sum
|B1|+|B2|+…+|Bd|
, a contradiction. This proves that the cut sets
Bi
are pairwise
disjoint.
The
Bi
are flipped one after the other and by definition of X, the dicut induced
by
Bi
is flippable if and only if all the elements in the downset of
Bi
with respect
to P but not in
Bi
were flipped before. Therefore, by listing the elements in the sets
B1,…,Bd
in this relative order, and ordering the elements within each
Bi
accord-
ing to their order in P, we obtain a linear extension L of P whose jumps are exactly
those pairs having elements in two consecutive sets
Bi
. It follows that there are
d−1
jumps in L, proving that
s(P)≤d−1
.
Combining these arguments shows that
s(P)=d−1
, and using Theorem11 we
obtain the claimed hardness result.
◻
7 Open Problems
Recall that Problem2 asks for a shortest flip sequence of directed cycles transform-
ing one
𝛼
-orientation X into another one Y, where we only allow flipping edges that
are oriented differently in X and Y. Since the set of edges that are oriented differently
in X and Y form an Eulerian subdigraph D of both X and Y, we have the following
natural question:
Question 1 What is the smallest number of directed cycles into which an Eulerian
digraph can be decomposed?
We have seen in Theorem3 that from a computational point of view, this prob-
lem is hard for general digraphs, but we wonder what happens when adding planar-
ity constraints. The aforementioned question can also be studied in terms of upper
bounds as a function of the number of vertices, which is related to the famous Hajós
conjecture on undirected Eulerian graphs, see [35]. Another interesting undirected
variant of Question1 is the following:
Question 2 Given a graph G with an Eulerian subgraph H, what is the smallest
number of cycles of G such that their symmetric difference is H?
Concerning our proof of Theorem7, we believe that for any bound on the size of
the cuts, the corresponding flip distance will be NP-hard to compute. On the other
hand, we use very particular graphs as gadgets, and we do not know the complexity
B1,…,Bi−1,Bi⧵{x},Bi+1,…,Bj−1,Bj⧵{x},Bj+1,…,Bd
140
Algorithmica (2021) 83:116–143
1 3
of the corresponding problem for planar
𝛼
-orientations. We think the following is an
interesting special case:
Question 3 Let X,Y be perfect matchings of a planar bipartite 3-connected graph
G. What is the complexity of determining the distance of X and Y with respect to
alternating cycles that are either a face or the symmetric difference of two incident
faces?
The feeling that this problem might be tractable is supported by the following
observation. It is not difficult to show that every height two poset with bipartite pla-
nar Hasse diagram has dimension at most two. It then follows from [55] that the
restriction of the Jump Number Problem to such posets is solvable in polynomial
time, and thus, the hardness reduction presented in the previous section fails.
Acknowledgements Open Access funding provided by Projekt DEAL. This work was initiated during
the workshop “Order & Geometry” 2018 in Ciążeń Palace. We thank the organizers and participants of
this workshop for the stimulating atmosphere.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License,
which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as
you give appropriate credit to the original author(s) and the source, provide a link to the Creative Com-
mons licence, and indicate if changes were made. The images or other third party material in this article
are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the
material. If material is not included in the article’s Creative Commons licence and your intended use is
not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission
directly from the copyright holder. To view a copy of this licence, visit http://creat iveco mmons .org/licen
ses/by/4.0/.
References
1. Aguiar, M., Ardila, F.: Hopf Monoids and Generalized Permutahedra (2017). arXiv:1709.07504
2. Aichholzer, O., Aurenhammer, F., Huemer, C., Vogtenhuber, B.: Gray code enumeration of plane
straight-line graphs. Graphs Combin. 23(5), 467–479 (2007)
3. Avis, D., Fukuda, K.: Reverse search for enumeration. Discrete Appl. Math. 65(1–3), 21–46 (1996)
4. Aichholzer, O., Mulzer, W., Pilz, A.: Flip distance between triangulations of a simple polygon is
NP-complete. Discrete Comput. Geom. 54(2), 368–389 (2015)
5. Bernardi, O., Fusy, É.: A bijection for triangulations, quadrangulations, pentagulations, etc. J. Com-
bin. Theory Ser. A 119(1), 218–244 (2012)
6. Bose, P., Hurtado, F.: Flips in planar graphs. Comput. Geom. 42(1), 60–80 (2009)
7. Blind, S., Knauer, K., Valicov, P.: Enumerating $k$-Arc-Connected Orientations (2019).
arXiv:1908.02050
8. Brehm, E.: 3-orientations and schnyder-3-tree-decompositions. Diploma Thesis, Freie Universität
Berlin (2000)
9. Brualdi, R.A.: Comments on bases in dependence structures. Bull. Aust. Math. Soc. 1, 161–167
(1969)
10. Bose, P., Verdonschot, S.:. A history of flips in combinatorial triangulations. In: Computational
Geometry: XIV Spanish Meeting on Computational Geometry, EGC 2011, Dedicated to Fer-
ran Hurtado on the Occasion of His 60th Birthday, Alcalá de Henares, Spain, June 27–30, 2011,
Revised Selected Papers, pp. 29–44 (2011)
11. Carmen Hernando, M., Hurtado, F., Noy, M.: Graphs of non-crossing perfect matchings. Graphs
Combin. 18(3), 517–532 (2002)
141
1 3
Algorithmica (2021) 83:116–143
12. Cleary, S., John, K.S.: Rotation distance is fixed-parameter tractable. Inf. Process. Lett. 109(16),
918–922 (2009)
13. Cleary, S., John, K.S.: A linear-time approximation for rotation distance. J. Graph Algorithms Appl.
14(2), 385–390 (2010)
14. Cardinal, J., Sacristán, V., Silveira, R.I.: A note on flips in diagonal rectangulations. Discrete Math.
Theor. Comput. Sci. 20(2), 14 (2018)
15. Ceballos, C., Santos, F., Ziegler, G.M.: Many non-equivalent realizations of the associahedron.
Combinatorica 35(5), 513–551 (2015)
16. De Loera, J., Rambau, J., Santos, F.: Triangulations: Structures for Algorithms and Applications,
vol. 25. Springer, Berlin (2010)
17. Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order, 2nd edn. Cambridge University
Press, New York (2002)
18. Felsner, Stefan: Lattice structures from planar graphs. Electron. J. Combin. 11(1), 24 (2004)
19. Felsner, S.: Rectangle and square representations of planar graphs. In: Thirty Essays on Geometric
Graph Theory, pp. 213–248. Springer, New York (2013)
20. Felsner, S., Knauer, K.: ULD-lattices and $\Delta $-bonds. Combin. Probab. Comput. 18(5), 707–
724 (2009)
21. Felsner, S., Knauer, K.: Distributive lattices, polyhedra, and generalized flows. Eur. J. Combin.
32(1), 45–59 (2011)
22. Felsner, S., Kleist, L., Mütze, T., Sering, L.: Rainbow cycles in flip graphs. In: 34th International
Symposium on Computational Geometry, SoCG 2018, June 11–14, 2018, Budapest, Hungary, pp.
38:1–38:14 (2018)
23. Felsner, S., Schrezenmaier, H., Steiner, R.: Equiangular polygon contact representations. In: Graph-
Theoretic Concepts in Computer Science—44th International Workshop, WG 2018, Cottbus, Ger-
many, June 27–29, 2018, Proceedings, pp. 203–215 (2018)
24. Felsner, S., Schrezenmaier, H., Steiner, R.: Pentagon contact representations. Electron. J. Combin.
25(3), 39 (2018)
25. Frank, A., Tardos, E.: Generalized polymatroids and submodular flows. Math. Program. 42(3), 489–
563 (1988)
26. Gilmer, P.M., Litherland, R.A.: The duality conjecture in formal knot theory. Osaka J. Math. 23(1),
229–247 (1986)
27. Gonçalves, D., Lévêque, B., Pinlou, A.: Triangle contact representations and duality. Discrete Com-
put. Geom. 48(1), 239–254 (2012)
28. Huemer, C., Hurtado, F., Noy, M., Omaña-Pulido, E.: Gray codes for non-crossing partitions and
dissections of a convex polygon. Discrete Appl. Math. 157(7), 1509–1520 (2009)
29. Houle, M.E., Hurtado, F., Noy, M., Rivera-Campo, E.: Graphs of triangulations and perfect match-
ings. Graphs Combin. 21(3), 325–331 (2005)
30. Iwata, S.: On matroid intersection adjacency. Discrete Math. 242(1–3), 277–281 (2002)
31. Knauer, K.: Partial orders on orientations via cycle flips. Master’s thesis, Faculty of Mathematics,
TU Berlin (2007)
32. Knauer, K.: Distributive lattices on graph orientations. In: Semigroups, Acts and Categories with
Applications to Graphs, Volume3 of Mathematical Studies (Tartu), pp. 79–91. Est. Mathematical
Society, Tartu (2008)
33. Kanj, I., Sedgwick, E., Xia, G.: Computing the flip distance between triangulations. Discrete Com-
put. Geom. 58(2), 313–344 (2017)
34. Luccio, F., Mesa Enriquez, A., Pagli, L.: Lower bounds on the rotation distance of binary trees. Inf.
Process. Lett 110(21), 934–938 (2010)
35. Lovász, L.: On covering of graphs. Theory of Graphs. In: Proceedings of the Colloquium Held at
Tihany, Hungary 1966, pp. 231–236 (1968)
36. Lam, T., Postnikov, A.: Alcoved polytopes. I. Discrete Comput. Geom. 38(3), 453–478 (2007)
37. Lubiw, A., Pathak, V.: Flip distance between two triangulations of a point set is NP-complete. Com-
put. Geom. 49, 17–23 (2015)
38. Li, M., Zhang, L.: Better approximation of diagonal-flip transformation and rotation transformation.
In: Computing and Combinatorics, 4th Annual International Conference, COCOON’98, Taipei, Tai-
wan, R.O.C., August 12–14, 1998, Proceedings, pp. 85–94 (1998)
39. Lam, P.C.B., Zhang, H.: A distributive lattice on the set of perfect matchings of a plane bipartite
graph. Order 20(1), 13–29 (2003)
40. Müller, H.: Alternating cycle-free matchings. Order 7(1), 11–21 (1990)
142
Algorithmica (2021) 83:116–143
1 3
41. Negami, S.: Diagonal flips in triangulations of surfaces. Discrete Math. 135(1–3), 225–232 (1994)
42. Papadimitriou, C.H.: The adjacency relation on the traveling salesman polytope is NP-complete.
Math. Program. 14(3), 312–324 (1978)
43. Péroche, B.: NP-completeness of some problems of partitioning and covering in graphs. Discrete
Appl. Math. 8(2), 195–208 (1984)
44. Plesník, J.: The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree
bound two. Inf. Process. Lett. 8(4), 199–201 (1979)
45. Postnikov, A.: Permutohedra, associahedra, and beyond. Int. Math. Res. Not. IMRN 6, 1026–1106
(2009)
46. Pournin, L.: The diameter of associahedra. Adv. Math. 259, 13–42 (2014)
47. Propp, J.: Lattice structure for orientations of graphs (2002). arXiv:math/0209005
48. Pilaud, V., Santos, F.: Quotientopes. arXiv:171105353 (2018)
49. Pulleyblank, W.R.: On minimizing setups in precedence constrained scheduling. Technical report,
University of Bonn, 1975. Technical Report 81105-OR
50. Propp, J., Wilson, D.: Coupling from the past: a user’s guide. In: Microsurveys in Discrete Probabil-
ity (Princeton, NJ, 1997), Volume41 of DIMACS Series in Discrete Mathematics and Theoretical
Computer Science, pp. 181–192. American Mathematical Society, Providence, RI (1998)
51. Rispoli, F.J., Cosares, S.: A bound of $4$ for the diameter of the symmetric traveling salesman poly-
tope. SIAM J. Discrete Math. 11(3), 373–380 (1998)
52. Rémila, E.: The lattice structure of the set of domino tilings of a polygon. Theor. Comput. Sci.
322(2), 409–422 (2004)
53. Ringel, G.: Über Geraden in allgemeiner Lage. Elem. Math. 12, 75–82 (1957)
54. Rogers, R.O.: On finding shortest paths in the rotation graph of binary trees. In: Proceedings of the
Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing
(Boca Raton, FL, 1999), vol. 137, pp. 77–95 (1999)
55. Steiner, G., Stewart, L.K.: A linear time algorithm to find the jump number of $2$-dimensional
bipartite partial orders. Order 3(4), 359–367 (1987)
56. Stanley, R.P.: Two poset polytopes. Discrete Comput. Geom. 1(1), 9–23 (1986)
57. Sleator, D.D., Tarjan, R.E., Thurston, W.P.: Rotation distance, triangulations, and hyperbolic geom-
etry. J. Am. Math. Soc. 1(3), 647–681 (1988)
58. Thurston, W.P.: Conway’s tiling groups. Am. Math. Monthly 97(8), 757–773 (1990)
59. Zhang, F.J., Guo, X.F.: Hamilton cycles in directed Euler tour graphs. Discrete Math. 64(2–3), 289–
298 (1987)
60. Zhang, W.J., Qian, J.G., Zhang, F.J.: Distance between $\alpha $-orientations of plane graphs by
facial cycle reversals. Acta Math. Sin. Engl. Ser. 35(4), 569–576 (2019)
Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published
maps and institutional affiliations.
Affiliations
OswinAichholzer1· JeanCardinal2· TonyHuynh3· KoljaKnauer4·
TorstenMütze5· RaphaelSteiner6 · BirgitVogtenhuber1
* Raphael Steiner
Oswin Aichholzer
oaich@ist.tugraz.at
Jean Cardinal
Tony Huynh
143
1 3
Algorithmica (2021) 83:116–143
Kolja Knauer
Torsten Mütze
torsten.mutze@warwick.ac.uk
Birgit Vogtenhuber
1 TU Graz, Graz, Austria
2 Université Libre de Bruxelles (ULB), Brussels, Belgium
3 Monash University, Clayton, Australia
4 Universitat de Barcelona (UB), Barcelona, Spain
5 University ofWarwick, Coventry, UK
6 TU Berlin, Berlin, Germany
