Flip distances between graph orientations

dc.contributor.authorAichholzer, Oswin
dc.contributor.authorCardinal, Jean
dc.contributor.authorHuynh, Tony
dc.contributor.authorKnauer, Kolja
dc.contributor.authorMütze, Torsten
dc.contributor.authorSteiner, Raphael
dc.contributor.authorVogtenhuber, Birgit
dc.date.accessioned2021-03-18T08:48:58Z
dc.date.available2021-03-18T08:48:58Z
dc.date.issued2020-07-27
dc.description.abstractFlip 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 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 two is NP -complete. 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 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).en
dc.description.sponsorshipTU Berlin, Open-Access-Mittel – 2020en
dc.description.sponsorshipDFG, 413902284, Kombinatorische Strukturen und Algorithmen in symmetrischen Graphenen
dc.identifier.eissn1432-0541
dc.identifier.issn0178-4617
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/12856
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-11656
dc.language.isoen
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subject.ddc004 Datenverarbeitung; Informatiken
dc.subject.otherflip distanceen
dc.subject.othergraph orientationen
dc.subject.otherα-Orientationen
dc.subject.otherflip graphsen
dc.subject.othercombinatorial objectsen
dc.titleFlip distances between graph orientationsen
dc.typeArticleen
dc.type.versionpublishedVersionen
dcterms.bibliographicCitation.doi10.1007/s00453-020-00751-1en
dcterms.bibliographicCitation.journaltitleAlgorithmicaen
dcterms.bibliographicCitation.originalpublishernameSpringerNatureen
dcterms.bibliographicCitation.originalpublisherplaceLondon [u.a.]en
dcterms.bibliographicCitation.pageend143en
dcterms.bibliographicCitation.pagestart116en
dcterms.bibliographicCitation.volume83en
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik::FG Diskrete Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.groupFG Diskrete Mathematikde
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
Aichholzer_etal_Flip_2021.pdf
Size:
2.47 MB
Format:
Adobe Portable Document Format

Collections