Complexity of polytope diameters via perfect matchings
Christian Nöbel, Raphael Steiner · Society for Industrial and Applied Mathematics eBooks · 2025
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 1984 Frieze and Teng [FT94] proved the first cornerstone result in this direction by establishing that computing the diameter of an input polytope is weakly NP-hard. In a recent breakthrough- paper, Sanita (FOCS 2018, [San18]) studied the diameter of a special class of graph-based polytopes, known as fractional matching polytopes, and showed that determining their diameters is NP-hard, thus establishing strong NP-hardness of computing the diameter of polytopes.