Flip distances between graph orientations [original]

Vol:.(1234567890)

Algorithmica (2021) 83:116–143

https://doi.org/10.1007/s00453-020-00751-1

1 3

Flip Distances Between Graph Orientations

OswinAichholzer, etal.[full author details at the end of the article]

Received: 25 June 2019 / Accepted: 15 July 2020 / Published online: 27 July 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

𝛼(

)

, 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 etal. (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, Chapter5]). 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. Section5 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 andMain 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.

Problem1 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

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:

2 2

Fig. 2 Two

𝛼

-orientations of a graph and a flip between them, where the values of

𝛼

are depicted on the

vertices

2 1

C1C2C3C4

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

Problem2 Given

G,𝛼,X,Y,k

as in Problem1, 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 toPerfect 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

form a perfect matching. This is illustrated in Fig.4. Conversely, given a perfect

matching M of G, orienting all edges of M from

and all the other edges from

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

(x)−1 if x∈V

2 2

Fig. 4 An

𝛼

-orientation of a bipartite graph and the corresponding perfect matching

Loading more pages...