Inapproximability of shortest paths on perfect matching polytopes

Jean Cardinal, Raphael Steiner

We consider the computational problem of finding short paths in the skeleton of the perfect matching polytope of a bipartite graph. We prove that unless $P=NP$, there is no polynom…