×
Papadimitriou, C. H.; Yannakakis, M.

The complexity of facets (and some facets of complexity). (English) Zbl 0571.68028

J. Comput. Syst. Sci. 28, 244-259 (1984).
The authors introduce a certain complexity class \(D^ P\) connected with combinatorial optimization problems and in particular with the facets of polytopes. \(D^ P\) is the class of all languages that are the intersection of a language in NP and a language in coNP.

Cited in 4 Reviews
Cited in 117 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
90C99 Mathematical programming
51M20 Polyhedra and polytopes; regular figures, division of spaces

Keywords:

complexity class; combinatorial optimization; facets of polytopes; NP; coNP
Cite Review PDF
Full Text: DOI

References:

[1] Balas, E., Facets of the knapsack polytope, Math. Programming, 8, 146-164 (1975) · Zbl 0316.90046
[2] Balas, E.; Zemel, E., Critical cutsets of graphs and canonical facets of set packing polytopes, Math. Oper. Res., 2, 15-20 (1977) · Zbl 0447.52010
[3] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[4] Chvàtal, V., Edmonds polytopes and weakly hamiltonian graphs, Math. Programming, 5, 29-40 (1973) · Zbl 0267.05118
[5] Chvàtal, V., On certain polytopes associated with graphs, J. Combin. Theory Ser. B, 18, 138-154 (1975) · Zbl 0277.05139
[6] Dantzig, G., Linear Programming and Extensions (1963), Princeton Univ. Press: Princeton Univ. Press Princeton, N. J · Zbl 0108.33103
[7] Dantzig, G. B.; Fulkerson, D. R.; Johnson, S. M., Solution of a large-scale traveling salesman problem, Oper. Res., 2, 393-410 (1954) · Zbl 1414.90372
[8] Doyen, J.; van Diest, V., New families of hypohamiltonian graphs, Discrete Math., 13, 225-236 (1975) · Zbl 0312.05114
[9] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[10] Golumbic, M. C., Algorithm Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0461.05037
[11] Grötschel, M., On the monotone symmetric travelling salesman problem: hypohamiltonian/hypotraceable graphs and facets, Math Oper. Res., 5, 285-292 (1980) · Zbl 0442.90070
[12] Grötschel, M.; Lovasz, L.; Schrijver, A., The Ellipsoid Method and Its Consequences in Combinatorial Optimization (1980), Bonn
[13] Grötschel, M.; Padberg, M. W., On the symmetric travelling salesman problem II: Lifting theorem and facets, Math. Programming, 16, 281-302 (1979) · Zbl 0413.90049
[14] Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0797.05064
[15] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum: Plenum New York), 85-103 · Zbl 0366.68041
[16] Karp, R. M.; Papadimitriou, C. H., On linear characterizations of combinatorial optimization problems, (Proc. 21st Annual Sympos. Found. Comput. Sci. (1980)), 1-9
[17] Kelly, D., The 3-irreducible partially ordered sets, Canad. J. Math., 29, 367-383 (1977) · Zbl 0357.06004
[18] Khacian, L. G., A polynomial algorithm for linear programming, Dokl. Akad. Nauk. SSSR, 1093-1096 (1979) · Zbl 0414.90086
[19] Leggett, E. W.; Moore, D. J., Optimization problems and the polynomial hierarchy, Theoret. Comput. Sci., 15, 279-289 (1981) · Zbl 0459.68016
[20] Lindgren, W. F., An infinite class of hypohamiltonian graphs, Amer. Math. Monthly, 74, 1087-1089 (1967) · Zbl 0158.42503
[21] Nemhauser, G. L.; Trotter, L. E., Properties of vertex packing and independence system polyhedra, Math. Programming, 6, 48-61 (1974) · Zbl 0281.90072
[22] Padberg, M. W., On the facial structure of set packing polyhedra, Math. Programming, 5, 199-215 (1973) · Zbl 0272.90041
[23] Padberg, M. W., On the complexity of set packing polyhedra, Ann. Discrete Math., 1, 421-434 (1977) · Zbl 0399.05017
[24] Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, N. J · Zbl 0503.90060
[25] Thomassen, C., Hypohamiltonian and hypotraceable graphs, Discrete Math., 9, 91-96 (1974) · Zbl 0278.05110
[26] Trotter, W. T.; Moore, J. I., Characterization problems for graphs, partially ordered sets, lattices and families of sets, Discrete Math., 16, 361-381 (1976) · Zbl 0356.06007
[27] Trotter, W. T.; Ross, J. A., For \(t\) ⩾ 3, Every t-Dimensional Partial Order Can Be Embedded in a \((t+ 1)\)-Irreducible Partial Order, (Technical report (1981), Univ. of North Carolina) · Zbl 0568.06002
[28] Wolsay, L. A., Further facet generating procedures for vertex packing polytopes, Math. Programming, 11, 158-163 (1976) · Zbl 0348.90148
[29] Yannakakis, M., The complexity of the partial order dimension problem, SIAM J. Algebraic Discrete Methods, 3, 351-358 (1982) · Zbl 0516.06001
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.