Inapproximability of shortest paths on perfect matching polytopes

• 成果类型: Article
• 署名作者: Cardinal, Jean; Steiner, Raphael
• 署名单位: Universite Libre de Bruxelles; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-02025-4
• 发表日期: 2025
• 页码: 147-163
• 关键词: Complexity

摘要

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 polynomial-time algorithm that computes a path of constant length between two vertices at distance two of the perfect matching polytope of a bipartite graph. Conditioned on P not equal NP, this disproves a conjecture by Ito et al. (SIAM J Discrete Math 36(2):1102-1123, 2022). Assuming the Exponential Time Hypothesis we prove the stronger result that there exists no polynomial-time algorithm computing a path of length at most (1/4 - o(1)) logN/loglogN between two vertices at distance two of the perfect matching polytope of an N-vertex bipartite graph. These results remain true if the bipartite graph is restricted to be of maximum degree three. The above has the following interesting implication for the performance of pivot rules for the simplex algorithm on simply-structured combinatorial polytopes: If P not equal NP, then for every simplex pivot rule executable in polynomial time and every constant k is an element of N there exists a linear program on a perfect matching polytope and a starting vertex of the polytope such that the optimal solution can be reached in two monotone non-degenerate steps from the starting vertex, yet the pivot rule will require at least k non-degenerate steps to reach the optimal solution. This result remains true in the more general setting of pivot rules for so-called circuit-augmentation algorithms.