The (monotone) diameter of a polytope is a fundamental parameter with important connections to the efficiency of the simplex method. Despite the central role played by this parameter in discrete and linear optimization, determining the precise complexity of computing the diameter of an input polytope remains a long-standing open problem. In 1994 Frieze and Teng (Comput. Complex. 4(3), 207–219 (1994)) proved the first cornerstone result in this direction by establishing that computing the diameter of an input polytope is weakly \(\textsf{NP}\) -hard. In a recent breakthrough-paper, Sanità (FOCS, IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). pp. 910–921. (2018)) studied the diameter of a special class of graph-based polytopes, known as fractional matching polytopes, and showed that determining their diameters is \(\textsf{NP}\) -hard, thus establishing strong \(\textsf{NP}\) -hardness of computing the diameter of polytopes. As our first main result, we show that computing the diameter of perfect matching polytopes (of bipartite graphs) is \(\textsf{NP}\) -hard, giving an alternative, short proof for the strong \(\textsf{NP}\) -hardness of polytope diameters. In particular this shows that computing the diameter is \(\textsf{NP}\) -hard even when restricting to 0/1-polytopes with totally unimodular constraint matrices. In our second main result, we give a precise graph-theoretic description of the monotone diameter of perfect matching polytopes and use this description to prove the novel result that computing the monotone diameter of an input polytope is strongly \(\textsf{NP}\) -hard. As a consequence of these results, we solve an open problem posed and reiterated by Sanità (2020), Diameter of Polytopes: Algorithmic and Combinatorial Aspects. (2020); Kafer PhD thesis. University of Waterloo, (2022); and Borgwardt, Grewe, Kafer, Lee and Sanità On the Hardness of Short and Sign-Compatible Circuit Walks. (2024) by proving the strong \(\textsf{NP}\) -hardness of computing the so-called circuit diameter of polytopes. The latter is a well-studied polytope invariant that has attracted a lot of attention in the last decade due to its connection with circuit-augmentation schemes for linear optimization. Finally, complementing these negative complexity results, we also present a positive algorithmic result for diameters of perfect matching polytopes: we prove that for every fixed integer k, the problem of deciding whether the perfect matching polytope of a bipartite graph has monotone diameter at most k can be solved in polynomial time. In other words, there is an XP-algorithm for computing the monotone diameter of bipartite perfect matching polytopes.
