Flip Distances Between Graph Orientations

Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, Birgit Vogtenhuber

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

2 Citations (Scopus)

Abstract

Flip graphs are a ubiquitous class of graphs, which encode relations on a set of combinatorial objects induced by elementary, local changes. 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 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 α-orientations of a planar graph G is at most 2 is NP-complete. This also holds in the special case of plane perfect matchings, where flips involve alternating cycles. 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, but if we only change sinks into sources, or vice-versa, then the problem can be solved in polynomial time.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Subtitle of host publication45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019; Catalonia; Spain; 19 June 2019 through 21 June 2019
EditorsIgnasi Sau, Dimitrios M. Thilikos
Place of PublicationSwitzerland
PublisherSpringer-Verlag London Ltd.
Pages120-134
Number of pages15
Volume11789
ISBN (Electronic)9783030307868
ISBN (Print)9783030307851
DOIs
Publication statusPublished - 12 Sep 2019
Externally publishedYes
Event45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019 - Catalonia, Spain
Duration: 19 Jun 201921 Jun 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Nature Switzerland
Volume11789 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019
CountrySpain
CityCatalonia
Period19/06/1921/06/19

Keywords

  • Flip distance
  • Graph orientation
  • α-orientation

Cite this