Abstract
We show that it isD P-hard to determine the combinatorial diameter of a polytope specified by linear inequalities with integer data. Our result partially resolves a long-term open question.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. R. Garey andD. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco, 1979.
R. M. Karp, Reducibility among combinatorial problems. InComplexity of Computer Computation ed.R. E. Miller andThatcher, Plenum, New York, 1972, 85–103.
G. Kalai,Subexponential Bound for the d-step Problem. Manuscript, IBM Almaden Research Center, 1991.
G. Kalai andD. J. Kleitman. A quasi-polynomial bound for diameter of graphs of polyhedra.Bull. Amer. Math. Soc. 26 (2) (April 1992), 315–316.
V. Klee, Polytope pairs and their relationship to linear programming.Acta Mathematica 133 (2) (October 1974), 1–25.
B. Korte andR. Schrader, On the existence of fast approximating scheme.Nonlinear Programming 4 (1981), 415–437.
D. G. Larman, Path on polytopes.Proc. Lond. Math. Soc. 30 (1970), 161–178.
C. H. Papadimitriou andM. Yannakakis, The complexity of facets.J. Comput. System Sci. 28, (1984), 244–259.
L. J. Stockmeyer, The polynomial-time hierarchy.Theoret. Comput. Sci. 3 (1977), 1–22.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Frieze, A.M., Teng, SH. On the complexity of computing the diameter of a polytope. Comput Complexity 4, 207–219 (1994). https://doi.org/10.1007/BF01206636
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01206636