Jean Cardinal (Université libre de Bruxelles): Shortest paths on polymatroids and hypergraphic polytopes

Abstract:
Base polytopes of polymatroids, also known as generalized permutohedra, are polytopes whose
edges are parallel to a vector of the form ei − ej We consider the following computational pro-
blem: 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 mini-
mum 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 polyma-
troids in Rn 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, to appear in Combinatorial Theory.

Before this lecture, starting at 4:45 p.m., there will be coffee and tea in Room 1404. 

Everyone is cordially invited. 

Signed: Prof. Dr. Torsten Mütze