Shortest paths on polymatroids
Base polytopes of polymatroids, also known as generalized permutohedra, are polytopes whose edges are parallel to a vector of the form e_i – e_j. We consider the following computational problem: Given two vertices of a generalized permutohedron P, find a shortest path between them on the skeleton of P. This captures many known flip distance problems, such as computing the minimum number of exchanges between two spanning trees of a graph, the rotation distance between binary search trees, the flip distance between acyclic orientations of a graph, or rectangulations of a square. We prove that this problem is NP-hard, even when restricted to very simple polymatroids in ℝ^n defined by O(n) inequalities. We also prove the APX-hardness of the shortest path problem when the polymatroid is a hypergraphic polytope, whose vertices are in bijection with acyclic orientations of a given hypergraph. The shortest path problem then amounts to computing the flip distance between two acyclic orientations of a hypergraph. On the positive side, we provide an exact polynomial-time algorithm for the flip distance between two acyclic orientations of any linear hypergraph.
Joint work with Raphael Steiner (ETH Zurich).
![[dot-sign]](res/antispam/full_stop.png)
de-mesmay
![[the-funny-at-sign]](res/antispam/commercial_at.png)
univ-eiffel