×

Enumerating vertices of covering polyhedra with totally unimodular constraint matrices. (English) Zbl 1432.68324

Summary: We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron \(P=P(A,\underline{1})=\{x\in \mathbb{R}^n \mid Ax\geq \underline{1},~x\geq \underline{0}\} \), when \(A\) is a totally unimodular matrix. Our algorithm is based on decomposing the hypergraph transversal problem for unimodular hypergraphs using Seymour’s decomposition of totally unimodular matrices and may be of independent interest.

MSC:

68R05 Combinatorics in computer science
05C65 Hypergraphs
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
52B55 Computational aspects related to convexity
68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. D. Abdullahi, Vertex Enumeration and Counting for Certain Classes of Polyhedra, Ph.D. thesis, Computing (Computer Algorithms), Leeds University, UK, 2003.
[2] D. Avis and K. Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete Comput. Geom., 8 (1992), pp. 295-313. · Zbl 0752.68082
[3] D. Avis and K. Fukuda, Reverse search for enumeration, Discrete Appl. Math., 65 (1996), pp. 21-46. · Zbl 0854.68070
[4] D. Avis, G. D. Rosenberg, R. Savani, and B. von Stengel, Enumeration of Nash equilibria for two-player games, Econom. Theory, 42 (2010), pp. 9-37. · Zbl 1182.91013
[5] A. Tamura, A. Shioura, and T. Uno, An optimal algorithm for scanning all spanning trees of undirected graphs, SIAM J. Comput., 26 (1997), pp. 678-692. · Zbl 0870.05066
[6] E. Boros, K. Elbassioni, V. Gurvich, and L. Khachiyan, Generating maximal independent sets for hypergraphs with bounded edge-intersections, in LATIN ’04: Proceedings of the 6th Latin American Symposium on Theoretical Informatics, 2004, pp. 488-498. · Zbl 1196.05057
[7] E. Boros, K. Elbassioni, V. Gurvich, and K. Makino, Generating vertices of polyhedra and related problems of monotone generation, in Proceedings of the Centre de Recherches Mathématiques at the Université de Montréal, Vol. 49, D. Avis, D. Bremner, and A. Deza, eds., 2009. · Zbl 1170.68619
[8] E. Boros, K. Elbassioni, V. Gurvich, and H. R. Tiwary, The negative cycles polyhedron and hardness of checking some polyhedral properties, Ann. Oper. Res., 188 (2011), pp. 63-76. · Zbl 1225.90143
[9] C. Berge, Hypergraphs, Elsevier-North Holand, Amsterdam, 1989. · Zbl 0674.05001
[10] D. Bremner, K. Fukuda, and A. Marzetta, Primal-dual methods for vertex and facet enumeration, Discrete Comput. Geom., 20 (1998), pp. 333-357. · Zbl 0910.68217
[11] J. C. Bioch and T. Ibaraki, Complexity of identification and dualization of positive boolean functions, Inform. Comput., 123 (1995), pp. 50-63. · Zbl 1096.68633
[12] M. R. Bussieck and M. E. Lübbecke, The vertex set of a 0/1 polytope is strongly \(\mathcal{P} \)-enumerable, Comput. Geom., 11 (1998), pp. 103-109. · Zbl 0912.68206
[13] V. Chvátal, Linear Programming, Freeman, San Francisco, CA, 1983. · Zbl 0537.90067
[14] C. N. Mishra and L. Pitt, Efficient read-restricted monotone cnf/dnf dualization by learning with membership queries, Mach. Learn., 37 (1999), pp. 89-110. · Zbl 0948.68097
[15] G. Cornuéjols, Combinatorial Optimization: Packing and Covering, CBMS-NSF Regional Conf. Ser. Appl. Math. 74, SIAM, Philadelphia, 2001. · Zbl 0972.90059
[16] M. E. Dyer and L. G. Proll, An algorithms for determining all extreme points of a convex polytope, Math. Program., 12 (1977), pp. 81-96. · Zbl 0378.90059
[17] M. E. Dyer, The complexity of vertex enumeration methods, Math. Oper. Res., 8 (1983), pp. 381-402. · Zbl 0531.90064
[18] T. Eiter and G. Gottlob, Identifying the minimal transversals of a hypergraph and related problems, SIAM J. Comput., 24 (1995), pp. 1278-1304. · Zbl 0842.05070
[19] T. Eiter, G. Gottlob, and K. Makino, New results on monotone dualization and generating hypergraph transversals, SIAM J. Comput., 32 (2003), pp. 514-537. · Zbl 1052.68101
[20] T. Eiter, Exact transversal hypergraphs and application to Boolean \(\mu \)-functions, J. Symbolic Comput., 17 (1994), pp. 215-225. · Zbl 0809.94032
[21] K. Elbassioni, K. Makino, and I. Rauf, Output-sensitive algorithms for enumerating minimal transversals for some geometric hypergraphs, in Proceedings of ESA, 2009, pp. 143-154. · Zbl 1256.68150
[22] K. Elbassioni, I. Rauf, and S. Ray, A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs, Theoret. Comput. Sci., 767 (2019), pp. 26-33. · Zbl 1417.68276
[23] M. L. Fredman and L. Khachiyan, On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms, 21 (1996), pp. 618-628. · Zbl 0864.68038
[24] V. Gurvich and L. Khachiyan, On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions, Discrete Appl. Math., 96-97 (1999), pp. 363-373. · Zbl 0953.06013
[25] L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, and V. Gurvich, Generating all vertices of a polyhedron is hard, Discrete Comput. Geom., 39 (2008), pp. 174-190. · Zbl 1147.05040
[26] L. Khachiyan, E. Boros, K. Elbassioni, V. Gurvich, and K. Makino, On the complexity of some enumeration problems for matroids, SIAM J. Discrete Math., 19 (2005), pp. 966-984. · Zbl 1104.05017
[27] M. M. Kanté, K. Khoshkhah, and M. Pourmoradnasseri, Enumerating minimal transversals of hypergraphs without small holes, in Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, Liverpool, UK, 2018, pp. 1-55. · Zbl 1516.05154
[28] A. Lehman, On the width-length inequality, mimeographic notes, Math. Program., 17 (1979), pp. 403-417. · Zbl 0418.90040
[29] E. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, Generating all maximal independent sets: NP-hardness and polynomial-time algorithms, SIAM J. Comput., 9 (1980), pp. 558-565. · Zbl 0445.68054
[30] L. Lovász, Combinatorial Optimization: Some Problems and Trends, DIMACS Technical Report 92-53, Rutgers University, New Brunswich, NJ, 1992.
[31] N. Mishra and L. Pitt, Generating all maximal independent sets of bounded-degree hypergraphs, in COLT ’97: Proceedings of the 10th Annual Conference on Computational Learning Theory, 1997, pp. 211-217.
[32] M. E. Pfetsch, The Maximum Feasible Subsystem Problem and Vertex-Facet Incidences of Polyhedra, Dissertation, TU Berlin, 2002. · Zbl 1114.52301
[33] J. S. Provan, Efficient enumeration of the vertices of polyhedra associated with network LP’s, Math. Program., 63 (1994), pp. 47-64. · Zbl 0792.90045
[34] A. Schrijver, Theory of Linear and Integer Programming, Wiley, New York, 1986. · Zbl 0665.90063
[35] R. Seidel, Output-Size Sensitive Algorithms for Constructive Problems in Computational Geometry, Computer Science, Cornell University, Ithacka, NY, 1986.
[36] P. D. Seymour, Decomposition of regular matroids, J. Combin. Theory Ser. B, 28 (1980), pp. 305-359. · Zbl 0443.05027
[37] K. Truemper, Matroid Decomposition, Academic Press, New York, 1992. · Zbl 0760.05001
[38] V. V. Vazirani, Approximation Algorithms, Springer-Verlag, New York, 2001. · Zbl 0999.68546
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.