SpringerLink - Journal Article

Generating All Vertices of a Polyhedron Is Hard

Leonid Khachiyan, Endre Boros¹, Konrad Borys¹, Khaled Elbassioni² and Vladimir Gurvich¹

(1)	RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ 08854-8003, USA

(2)	Department 1, Max-Planck-Institut für Informatik, 66123 Saarbrücken, Germany

Received: 21 July 2005 Revised: 8 June 2006 Published online: 5 March 2008

Communicated by Günter M. Ziegler.

Abstract We show that generating all negative cycles of a weighted graph is a hard enumeration problem, in both the directed and undirected cases. More precisely, given a family of negative (directed) cycles, it is an NP-complete problem to decide whether this family can be extended or there are no other negative (directed) cycles in the graph, implying that (directed) negative cycles cannot be generated in polynomial output time, unless P=NP. As a corollary, we solve in the negative two well-known generating problems from linear programming: (i) Given an infeasible system of linear inequalities, generating all minimal infeasible subsystems is hard. Yet, for generating maximal feasible subsystems the complexity remains open. (ii) Given a feasible system of linear inequalities, generating all vertices of the corresponding polyhedron is hard. Yet, in the case of bounded polyhedra the complexity remains open. Equiva lently, the complexity of generating vertices and extreme rays of polyhedra remains open.

This research was partially supported by the National Science Foundation (Grant IIS-0118635), and by DIMACS, the National Science Foundation’s Center for Discrete Mathematics and Theoretical Computer Science. An extended abstract of this paper appears in the Proceedings of the ACM–SIAM Symposium on Discrete Algorithms, Miami, Florida, January 22–24, 2006.

Our friend and colleague, Leo Khachiyan, passed away with tragic suddenness while we were preparing this manuscript.

Endre Boros (Corresponding author)
Email: boros@rutcor.rutgers.edu

Konrad Borys
Email: kborys@rutcor.rutgers.edu

Khaled Elbassioni
Email: elbassio@mpi-sb.mpg

Vladimir Gurvich
Email: gurvich@rutcor.rutgers.edu

References

1.	Abdullahi, S.D.: Vertex enumeration and counting for certain classes of polyhedra. Ph.D. thesis, Computing (Computer Algorithms), Leeds University (2003)

2.	Avis, D., Bremner, B., Seidel, R.: How good are convex hull algorithms. Comput. Geom. Theory Appl. 7, 265–302 (1997)

3.	Avis, D., Fukuda, K.: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Comput. Geom. 8(3), 295–313 (1992)

4.	Avis, D., Fukudam, K.: Reverse search for enumeration. Discrete Appl. Math. 65(1–3), 21–46 (1996)

5.	Amaldi, E., Pfetsch, M.E., Trotter, L.E.: On the maximum feasible subsystem problem, IISs and IIS-hypergraphs. Math. Program. 95, 533–554 (2003)

6.	Balinski, M.L.: An algorithm for finding all vertices of convex polyhedral sets. SIAM J. Appl. Math. 9, 72–81 (1961)

7.	Boros, E., Elbassioni, K., Gurvich, V., Khachiyan, L.: Enumerating minimal dicuts and strongly connected subgraphs and related geometric problems. In: Bienstock, D., Nemhauser, G. (eds.) Integer Programming and Combinatorial Optimization, 10th International IPCO Conference. Lecture Notes in Computer Science, vol. 3064, pp. 152–162. Springer, Berlin (2004). (An extended version is to appear in Algorithmica)

8.	Berge, C.: Hypergraphs. Elsevier-North Holland, Amsterdam (1989)

9.	Bremner, D., Fukuda, K., Marzetta, A.: Primal–dual methods for vertex and facet enumeration. Discrete Comput. Geom. 20, 333–357 (1998)

10.	Bussieck, M.R., Lübbecke, M.E.: The vertex set of a 0/1 polytope is strongly ℘-enumerable. Comput. Geom. Theory Appl. 11(2), 103–109 (1998)

11.	Bremner, D.: Incremental convex hull algorothms are not output sensitive. Discrete Comput. Geom. 21, 57–68 (1999)

12.	Charnes, A., Cooper, W.W., Henderson, A.: An Introduction to Linear Programming. Wiley, New York (1953)

13.	Chazelle, B.: An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom. 10, 377–409 (1993)

14.	Chakravarti, N.: Some results concerning post-infeasibility analysis. Eur. J. Oper. Res. 73, 139–143 (1994)

15.	Chvátal, V.: Linear Programming. Freeman, San Francisco (1983)

16.	Chand, D.R., Kapur, S.S.: An algorithm for convex polytopes. J. Assoc. Comput. Mach. 17(1), 78–86 (1970)

17.	Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151–158 (1971)

18.	Dyer, M.E.: The complexity of vertex enumeration methods. Math. Oper. Res. 8, 381–402 (1983)

19.	Dyer, M.E., Proll, L.G.: An algorithm for determining all extreme points of a convex polytope. Math. Program. 12, 81–96 (1977)

20.	Eiter, T., Gottlob, G.: Identifying the minimal transversals of a hypergraph and related problems. SIAM J. Comput. 24, 1278–1304 (1995)

21.	Farkas, J.: Theorie der einfachen ungleichungen. J. Rein. Angew. Math. 124, 1–27 (1901)

22.	Fredman, M., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms. J. Algorithms 21, 618–628 (1996)

23.	Floyd, R.W.: Algorithm 97: Shortest path. Commun. Assoc. Comput. Mach. 5, 345 (1962)

24.	Fukuda, K., Liebling, Th.M., Margot, F.: Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron. CGTA 8, 1–12 (1997)

25.	Gallai, T.: Maximum-minimum Sätze über Graphen. Acta Math. Acad. Sci. Hung. 9, 395–434 (1958)

26.	Gleeson, J., Ryan, J.: Identifying minimally infeasible subsystems of inequalities. ORSA J. Comput. 2(1), 61–63 (1990)

27.	Johnson, D.S., Preparata, F.P.: The densest hemisphere problem. Theor. Comput. Sci. 6, 93–107 (1978)

28.	Johnson, D.S., Papadimitriou, Ch.H.: On generating all maximal independent sets. Inf. Process. Lett. 27, 119–123 (1988)

29.	Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci. 44, 169–188 (1986)

30.	Khachiyan, L.: A polynomial algorithm in linear programming. Sov. Math. Dokl. 20, 191–194 (1979)

31.	Lovász, L.: Combinatorial optimization: some problems and trends. DIMACS Technical Report 92-53, Rutgers University (1992)

32.	Lawler, E., Lenstra, J.K., Rinnooy Kan, A.H.G.: Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM J. Comput. 9, 558–565 (1980)

33.	Mattheiss, T.H.: An algorithm for determining irrelevant constraints and all vertices in systems of linear inequalities. Oper. Res. 21, 247–260 (1973)

34.	Motzkin, T.S., Raiffa, H., Thompson, G.L., Thrall, R.M.: The double description method. In: H.W. Kuhn and A.W. Tucker (eds.) Contributions to the Theory of Games, vol. II, pp. 51–73 (1953)

35.	Pfetsch, M.E.: The maximum feasible subsystem problem and vertex-facet incidences of polyhedra. Dissertation, TU Berlin (2002)

36.	Provan, J.S.: Efficient enumeration of the vertices of polyhedra associated with network lp’s. Math. Program. 63(1), 47–64 (1994)

37.	Read, R.C., Tarjan, R.E.: Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5, 237–252 (1975)

38.	Ryan, J.: IIS-hypergraphs. SIAM J. Discrete Math. 9(4), 643–653 (1996)

39.	Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)

40.	Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. A. Springer, Berlin (2003)

41.	Seidel, R.: Output-size sensitive algorithms for constructive problems in computational geometry. Computer Science. Cornell University, Ithaka (1986)

42.	Swart, G.: Finding the convex hull facet by facet. J. Algorithms 6, 17–48 (1985)

43.	Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8, 410–421 (1979)

44.	Warshall, S.: A theorem on boolean matrices. J. Assoc. Comput. Mach. 9, 11–12 (1962)