Complexity of polytope diameters via perfect matchings

• 成果类型: Article; Early Access
• 署名作者: Nobel, Christian; Steiner, Raphael
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02324-6
• 发表日期: 2026-02-19
• 关键词: CIRCUIT DIAMETER; augmentation; bipartite

摘要

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 NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{NP}$$\end{document}-hard. In a recent breakthrough-paper, Sanit & agrave; (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 NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{NP}$$\end{document}-hard, thus establishing strong NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{NP}$$\end{document}-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 NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{NP}$$\end{document}-hard, giving an alternative, short proof for the strong NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{NP}$$\end{document}-hardness of polytope diameters. In particular this shows that computing the diameter is NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{NP}$$\end{document}-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 NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{NP}$$\end{document}-hard. As a consequence of these results, we solve an open problem posed and reiterated by Sanit & agrave; (2020), Diameter of Polytopes: Algorithmic and Combinatorial Aspects. (2020); Kafer PhD thesis. University of Waterloo, (2022); and Borgwardt, Grewe, Kafer, Lee and Sanit & agrave; On the Hardness of Short and Sign-Compatible Circuit Walks. (2024) by proving the strong NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{NP}$$\end{document}-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.