NP-hard graph problems and boundary classes of graphs. (English) Zbl 1143.68058
Summary: Any graph problem, which is NP-hard in general graphs, becomes polynomial-time solvable when restricted to graphs in special classes. When does a difficult problem become easy? To answer this question we study the notion of boundary classes. In the present paper we define this notion in its most general form, describe several approaches to identify boundary classes and apply them to various graph problems.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | Alekseev, V. E., On the local restrictions effect on the complexity of finding the graph independence number, (Combinatorial-Algebraic Methods in Applied Mathematics (1983), Gorkiy Univ. Press: Gorkiy Univ. Press Gorky), 3-13, (in Russian) |
| [2] | Alekseev, V. E., On easy and hard hereditary classes of graphs with respect to the independent set problem, Discrete Appl. Math., 132, 17-26 (2003) · Zbl 1029.05140 |
| [3] | Alekseev, V. E.; Korobitsyn, D. V., On the complexity of some problems on hereditary classes of graphs, Diskret. Mat., 4, 4, 34-40 (1992), (in Russian) · Zbl 0804.05066 |
| [4] | Alekseev, V. E.; Korobitsyn, D. V.; Lozin, V. V., Boundary classes of graphs for the dominating set problem, Discrete Math., 285, 1-6 (2004) · Zbl 1121.05081 |
| [5] | Alimonti, P.; Kann, V., Some APX-completeness results for cubic graphs, Theoret. Comput. Sci., 237, 123-134 (2000) · Zbl 0939.68052 |
| [6] | Bandelt, H. J.; Mulder, H. M., Distance-hereditary graphs, J. Combin. Theory Ser. B, 41, 2, 182-208 (1986) · Zbl 0605.05024 |
| [7] | Beineke, L. W., Characterizations of derived graphs, J. Combin. Theory, 9, 129-135 (1970) · Zbl 0202.55702 |
| [8] | Benzer, S., On the topology of the genetic fine structure, Proc. Natl. Acad. Sci. USA, 45, 1607-1620 (1959) |
| [9] | Boliac, R.; Lozin, V., On the clique-width of graphs in hereditary classes, Lecture Notes in Comput. Sci., 2518, 44-54 (2002) · Zbl 1020.05046 |
| [10] | Boliac, R.; Lozin, V., Independent domination in finitely defined classes of graphs, Theoret. Comput. Sci., 301, 271-284 (2003) · Zbl 1028.68061 |
| [11] | Boliac, R.; Cameron, K.; Lozin, V., On the computing the dissociation number of bipartite graphs, Ars Combin., 72, 241-253 (2004) · Zbl 1075.05066 |
| [12] | R.B. Borie, R.G. Parker, C.A. Tovey, Solving problems on recursively constructed graphs, ACM Comput. Surveys (in press) (available online at http://cs.ua.edu/691Borie/ComputingSurveys.pdf; R.B. Borie, R.G. Parker, C.A. Tovey, Solving problems on recursively constructed graphs, ACM Comput. Surveys (in press) (available online at http://cs.ua.edu/691Borie/ComputingSurveys.pdf · Zbl 0753.05062 |
| [13] | Chudnovsky, M.; Robertson, N.; Seymour, P. D.; Thomas, R., The Strong Perfect Graph Theorem, Ann. of Math., 164, 51-229 (2006) · Zbl 1112.05042 |
| [14] | Courcelle, B.; Makowsky, J. A.; Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst., 33, 125-150 (2000) · Zbl 1009.68102 |
| [15] | Damaschke, P.; Müller, H.; Kratsch, D., Domination in convex and chordal bipartite graphs, Inform. Process. Lett., 36, 231-236 (1990) · Zbl 0706.68055 |
| [16] | Farber, M., Independent domination in chordal graphs, Oper. Res. Lett., 1, 131-138 (1982) · Zbl 0495.05053 |
| [17] | Fishburn, P. C., Interval Orders and Interval Graphs (1985), John Wiley & Sons, Ltd.: John Wiley & Sons, Ltd. Chichester · Zbl 0216.30401 |
| [18] | Foldes, S.; Hammer, P. L., Split graphs, Congr. Numer., 19, 311-315 (1977) · Zbl 0407.05071 |
| [19] | Garey, M. G.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences (1979), W.H. Freeman and Co.: W.H. Freeman and Co. San Francisco, Calif. · Zbl 0411.68039 |
| [20] | Golumbic, M. C.; Rotics, U., On the clique-width of some perfect graph classes, Internat. J. Found. Comput. Sci., 11, 423-443 (2000) · Zbl 1320.05090 |
| [21] | Golumbic, M. C., (Algorithmic Graph Theory and Perfect Graphs. Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol. 57 (2004), Elsevier Science B.V.: Elsevier Science B.V. Amsterdam) · Zbl 1050.05002 |
| [22] | Hoffman, A. J.; Kolen, A. W.J.; Sakarovitch, M., Totally-balanced and greedy matrices, SIAM J. Algebr. Discrete Methods, 6, 721-730 (1985) · Zbl 0573.05041 |
| [23] | Holyer, I., The NP-completeness of edge-coloring, SIAM J. Comput., 10, 718-720 (1981) · Zbl 0473.68034 |
| [24] | Itai, A.; Papadimitriou, C. H.; Szwarcfiter, J. L., Hamilton paths in grid graphs, SIAM J. Comput., 11, 676-686 (1982) · Zbl 0506.05043 |
| [25] | M. Kaminski, V. Lozin, M. Milanic, Recent developments on graphs of bounded clique-width, RUTCOR Research Report 6-2007, Rutgers University, 2007 (available online at http://rutcor.rutgers.edu/ rrr/2007.html; M. Kaminski, V. Lozin, M. Milanic, Recent developments on graphs of bounded clique-width, RUTCOR Research Report 6-2007, Rutgers University, 2007 (available online at http://rutcor.rutgers.edu/ rrr/2007.html · Zbl 1211.05165 |
| [26] | Kobler, D.; Rotics, U., Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size, Algorithmica, 37, 327-346 (2003) · Zbl 1082.68592 |
| [27] | Kochol, M.; Lozin, V.; Randerath, B., The 3-colorability problem on graphs with maximum degree four, SIAM J. Comput., 32, 1128-1139 (2003) · Zbl 1026.05040 |
| [28] | König, D., Über Graphen und ihre Anwendungen auf Determinantentheorie und Mengenlehre, Math. Ann., 77, 435-465 (1916) · JFM 46.0146.03 |
| [29] | Korobitsyn, D. V., On the complexity of determining the domination number in monogenic classes of graphs, Diskret. Mat., 2, 3, 90-96 (1990), (in Russian). Translation in Discrete Math. Appl. 2 (2) (1992) 191-199 · Zbl 0729.05047 |
| [30] | Lozin, V.; Gerber, M., On the jump number problem in hereditary classes of bipartite graphs, Order, 17, 377-385 (2000) · Zbl 0987.05088 |
| [31] | Lozin, V., On maximum induced matchings in bipartite graphs, Inform. Process. Lett., 81, 7-11 (2002) · Zbl 1046.68081 |
| [32] | Lozin, V.; Rautenbach, D., On the band-, tree- and clique-width of graphs with bounded vertex degree, SIAM J. Discrete Math., 18, 195-206 (2004) · Zbl 1081.05098 |
| [33] | Lozin, V.; Rautenbach, D., Chordal bipartite graphs of bounded tree- and clique-width, Discrete Math., 283, 151-158 (2004) · Zbl 1044.05060 |
| [34] | Maffray, F.; Preissmann, M., On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs, Discrete Math., 162, 313-317 (1996) · Zbl 0870.05021 |
| [35] | Mahadev, N. V.R.; Peled, U. N., Threshold graphs and related topics, (Annals of Discrete Mathematics, vol. 56 (1995), North-Holland Publishing Co.: North-Holland Publishing Co. Amsterdam) · Zbl 0852.05001 |
| [36] | Müller, H., Alternating cycle-free matchings, Order, 7, 11-21 (1990) · Zbl 0805.68091 |
| [37] | Müller, H.; Brandstädt, A., The NP-completeness of steiner tree and dominating set for chordal bipartite graphs, Theoret. Comput. Sci., 53, 257-265 (1987) · Zbl 0638.68062 |
| [38] | Müller, H., Hamiltonian circuits in chordal bipartite graphs, Discrete Math., 156, 291-298 (1996) · Zbl 0856.68113 |
| [39] | Murphy, O. J., Computing independent sets in graphs with large girth, Discrete Appl. Math., 35, 167-170 (1992) · Zbl 0769.05053 |
| [40] | Randerath, B.; Schiermeyer, I.; Tewes, M., Three-colourability and forbidden subgraphs. II. Polynomial algorithms, Discrete Math., 251, 137-153 (2002) · Zbl 0999.05042 |
| [41] | Randerath, B.; Schiermeyer, I., 3-colorability \(\in P\) for \(P_6\)-free graphs, Discrete Appl. Math., 136, 299-313 (2004) · Zbl 1035.05042 |
| [42] | Trotter, W. T., Combinatorics and Partially Ordered Sets. Dimension Theory (1992), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 0764.05001 |
| [43] | Yannakakis, M.; Gavril, F., Edge dominating sets in graphs, SIAM J. Appl. Math., 38, 364-372 (1980) · Zbl 0455.05047 |
| [44] | Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM J. Algebr. Discrete Methods, 2, 77-79 (1981) · Zbl 0496.68033 |
| [45] | Zverovich, I., Satgraphs and independent domination, Theoret. Comput. Sci., 352, 47-56 (2006) · Zbl 1086.68048 |
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.
