  We prove that the computation of a combinatorial shortest path between two
vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard.
This resolves an open problem raised by Cardinal. A graph associahedron is a
generalization of the well-known associahedron. The associahedron is obtained
as the graph associahedron of a path. It is a tantalizing and important open
problem in theoretical computer science whether the computation of a
combinatorial shortest path between two vertices of the associahedron can be
done in polynomial time, which is identical to the computation of the flip
distance between two triangulations of a convex polygon, and the rotation
distance between two rooted binary trees. Our result shows that a certain
generalized approach to tackling this open problem is not promising. As a
corollary of our theorem, we prove that the computation of a combinatorial
shortest path between two vertices of a polymatroid base polytope cannot be
done in polynomial time unless P = NP. Since a combinatorial shortest path on
the matroid base polytope can be computed in polynomial time, our result
reveals an unexpected contrast between matroids and polymatroids.
