The Library
Flip distances between graph orientations
Tools
Aichholzer, Oswin, Cardinal, Jean, Huynh, Tony, Knauer, Kolja, Mutze, Torsten, Steiner, Raphael and Vogtenhuber, Birgit (2020) Flip distances between graph orientations. Algorithmica . doi:10.1007/s00453020007511 (In Press)

PDF
WRAPFlipdistancesbetweengraphorientationsMutze2020.pdf  Published Version  Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1591Kb)  Preview 
Official URL: https://doi.org/10.1007/s00453020007511
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 orientations of simple graphs, where flips consist of reversing the direction of some edges. More precisely, we consider socalled $\alpha$orientations of a graph $G$, in which every vertex $v$ has a specified outdegree $\alpha(v)$, and a flip consists of reversing all edges of a directed cycle. We prove that deciding whether the flip distance between two $\alpha$orientations of a planar graph $G$ is at most two is \NPcomplete. This also holds in the special case of perfect matchings, where flips involve alternating cycles. This problem amounts to finding geodesics on the common base polytope of two partition matroids, or, alternatively, on an alcoved polytope. It therefore provides an interesting 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 viceversa, 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, Qian, and Zhang (Acta. Math. Sin.English Ser., 2019).
Item Type:  Journal Article  

Subjects:  Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software 

Divisions:  Faculty of Science > Computer Science  
Library of Congress Subject Headings (LCSH):  Graph theory  Data processing, Combinatorial geometry, Polytopes  
Journal or Publication Title:  Algorithmica  
Publisher:  Springer  
ISSN:  01784617  
Official Date:  27 July 2020  
Dates: 


Date of first compliant deposit:  7 October 2020  
DOI:  10.1007/s00453020007511  
Status:  Peer Reviewed  
Publication Status:  In Press  
Access rights to Published version:  Open Access  
Open Access Version: 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 
Downloads
Downloads per month over past year