Flip Distances Between Graph Orientations

Area of Science:

• Discrete Mathematics
• Graph Theory
• Computational Complexity

Background:

• Flip graphs model local changes in combinatorial objects, with applications in geometry and combinatorics.
• Flip distance quantifies the minimum number of local changes (flips) to transform one object into another.
• Orientations of graphs, specifically k-orientations and orientations with specified cycle properties, are studied.

Purpose of the Study:

• To investigate the computational complexity of flip distance problems on graph orientations.
• To analyze the intractability of finding geodesics on combinatorial polytopes related to graph orientations.
• To explore polynomial-time solvable cases within the broader framework of flip distance computations.

Main Methods:

• Proving NP-completeness for deciding if the flip distance between two k-orientations of a planar graph is at most two.
• Relating flip distance problems to finding geodesics on partition and alcoved polytopes.
• Utilizing the distributive lattice structure of flip graphs for specific cases (sink-source flips).

Main Results:

• Deciding flip distance for k-orientations of planar graphs is NP-complete, even for perfect matchings.
• The problem is computationally intractable despite connections to geodesics on combinatorial polytopes.
• A polynomial-time solution exists for flip distances when flips are restricted to changing sinks to sources or vice-versa.

Conclusions:

• Flip distance problems on graph orientations exhibit significant computational complexity.
• The study highlights the intractability of geodesic problems on related polytopes.
• Restricted flip operations on graph orientations can lead to efficient algorithmic solutions.