  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$. 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 $\mathbb{R}^n$ defined by $O(n)$ inequalities. Assuming $P\not=
NP$, this rules out the existence of an efficient simplex pivoting rule that
performs a minimum number of nondegenerate pivoting steps to an optimal
solution of a linear program, even when the latter defines a polymatroid. We
also prove that the shortest path problem is inapproximable when the
polymatroid is specified via an evaluation oracle for a corresponding
submodular function, strengthening a recent result by Ito et al. (ICALP'23).
More precisely, we 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 a polynomial-time approximation
algorithm for the problem of computing the flip distance between two acyclic
orientations of a hypergraph, where the approximation factor is the maximum
codegree of the hypergraph. Our result implies an exact polynomial-time
algorithm for the flip distance between two acyclic orientations of any linear
hypergraph.
