Shortest paths on polymatroids and hypergraphic polytopes

Base polytopes of polymatroids, also known as generalized permutohedra, are polytopes whose edges are parallel to a vector of the form \(\mathbf{e}_i - \mathbf{e}_j\), where the \(\{\mathbf{e}_i\}_{i\in [n]}\) are the canonical basis vectors of \(\mathbb{R}^n\). We consider the following computational problem: Given two vertices of a generalized permutohedron \(P\), determine the length of a shortest path between them on the skeleton of \(P\), where the length of a path is its number of edges. 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 general problem is \NP-hard, even when restricted to very simple polymatroids in \(\mathbb{R}^n\) defined by \(O(n)\) inequalities. Assuming \(\operatorname{P}\not= \operatorname{NP}\), this shows that even when maximizing a linear functional over a polymatroid, we cannot hope for the existence of a computationally efficient simplex pivoting rule that performs a minimum number of nondegenerate pivoting steps to an optimal solution. Such results have previously been shown only for other, arguably more complicated classes of polytopes. We also prove that the shortest path problem is inapproximable when the polymatroid is specified via an evaluation oracle for a corresponding submodular function, which strengthens a recent result by Ito, Kakimura, Kamiyama, Kobayashi, Maezawa, Nozaki, and Okamoto (ICALP'23). More precisely, we prove that it is \NP-hard to approximate the length of a shortest path to within a factor \((1+\varepsilon)\) for some absolute constant \(\varepsilon›0\), even 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 a polynomial-time algorithm which, given any pair of acyclic orientations of a hypergraph, computes a connecting path whose length approximates the length of a shortest path to within a factor bounded by the maximum codegree of the hypergraph. Our result implies in particular an exact polynomial-time algorithm for computing shortest flip sequences between acyclic orientations of any linear hypergraph.Mathematics Subject Classifications: 90C05, 90C08, 90C27, 90C35, 90C49, 90C57, 90C60, 05C50, 05C65, 05B35, 52B40Keywords: Polymatroids, Generalized permutahedra, Hypergraphic polytopes, Simplex method, Shortest paths, Polytope diameter, Polytope skeleton, Flip distance, Combinatorial reconfiguration