On easy and hard hereditary classes of graphs with respect to the independent set problem. (English) Zbl 1029.05140
Summary: We introduce the concept of a boundary class, which is a helpful tool for classification of hereditary classes of graphs according to the complexity of the independent set problem. It is shown that in a class \(X\) defined by a finite set of forbidden induced subgraphs, the problem is NP-hard if and only if \(X\) includes a boundary class. The paper presents a particular boundary class and establishes several new polynomially solvable cases for the independent set problem.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
References:
| [1] | Alekseev, V. E., Hereditary classes and coding of graphs, (Jablonskij, S. V., Problems of Cybernetics, Vol. 39 (1982), Nauka: Nauka Moscow), 151-164, (in Russian) · Zbl 0521.94011 |
| [2] | V.E. Alekseev, On the local restrictions effect on the complexity of finding the graph independence number, in: A.A. Markov (Ed.), Combinatorial-Algebraic Methods in Applied Mathematics, Gorkiy University Press, Gorky, 1983, pp. 3-13 (in Russian).; V.E. Alekseev, On the local restrictions effect on the complexity of finding the graph independence number, in: A.A. Markov (Ed.), Combinatorial-Algebraic Methods in Applied Mathematics, Gorkiy University Press, Gorky, 1983, pp. 3-13 (in Russian). |
| [3] | V.E. Alekseev, On the number of maximal independence sets in graphs from hereditary classes, in: V.N. Shevchenko (Ed.), Combinatorial-Algebraic Methods in Applied Mathematics, Gorkiy University Press, Gorky, 1991, pp. 5-8 (in Russian).; V.E. Alekseev, On the number of maximal independence sets in graphs from hereditary classes, in: V.N. Shevchenko (Ed.), Combinatorial-Algebraic Methods in Applied Mathematics, Gorkiy University Press, Gorky, 1991, pp. 5-8 (in Russian). |
| [4] | Alekseev, V. E., A polynomial algorithm for finding the largest independent sets in fork-free graphs, Discrete Anal. Oper. Res. Ser. 1, 6, 4, 3-19 (1999), (in Russian) · Zbl 0931.05078 |
| [5] | Alekseev, V. E.; Korobitsyn, D. V., Complexity of some problems on hereditary classes of graphs, Discrete Math., 4, 4, 34-40 (1992), (in Russian) · Zbl 0804.05066 |
| [6] | Arbib, C.; Mosca, R., On \((P_5\),diamond)-free graphs, Discrete Math., 250, 1-22 (2002) · Zbl 1004.05027 |
| [7] | Balas, E.; Yu, Ch. S., On graphs with polynomially solvable maximum-weight clique problem, Networks, 19, 247-253 (1989) · Zbl 0661.05036 |
| [8] | Brandstädt, A.; Lozin, V. V., A note on \(α\)-redundant vertices in graphs, Discrete Appl. Math., 108, 301-308 (2001) · Zbl 0968.05058 |
| [9] | Gerber, M. U.; Lozin, V. V., On the stable set problem in special \(P_5\)-free graphs, Discrete Appl. Math., 125, 215-224 (2003) · Zbl 1028.05103 |
| [10] | D.V. Korobitsyn, On the complexity of determining the domination number in monogenic classes of graphs, Diskret. Mat. 2(3) (1990) 90-96 (in Russian, translation in Discrete Math. Appl. 2(2) (1992) 191-199).; D.V. Korobitsyn, On the complexity of determining the domination number in monogenic classes of graphs, Diskret. Mat. 2(3) (1990) 90-96 (in Russian, translation in Discrete Math. Appl. 2(2) (1992) 191-199). · Zbl 0729.05047 |
| [11] | Minty, G. J., On maximal independent sets in claw-free graphs, J. Combin Theory Ser. B, 28, 3, 284-304 (1980) · Zbl 0434.05043 |
| [12] | Mosca, R., Polynomial algorithms for the maximum stable set problem on particular classes of \(P_5\)-free graphs, Inform. Process. Lett., 61, 137-143 (1997) · Zbl 1337.68136 |
| [13] | Poljak, S., A note on stable sets and coloring of graphs, Comment. Math. Univ. Carolin., 15, 307-309 (1974) · Zbl 0284.05105 |
| [14] | Sbihi, N., Algorithme de recherche d’un stable set de cardinalite maximum dans un graphe sans etoile, Discrete Math., 29, 505-517 (1980) · Zbl 0444.05049 |
| [15] | Tarjan, R. E., Decomposition by clique separators, Discrete Math., 55, 221-232 (1985) · Zbl 0572.05039 |
| [16] | Tsukiyama, S.; Ide, M.; Ariochi, H.; Shirakawa, I., A new algorithm for generating all the maximal independent sets, SIAM J. Comput., 6, 3, 505-517 (1977) · Zbl 0364.05027 |
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.
