×

A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs. (English) Zbl 1369.05159

Summary: The maximum independent set problem is known to be NP-hard in general. In the last decades lots of effort were spent to find polynomial-time algorithms for \(P_t\)-free graphs. A recent result presents such an algorithm for \(P_5\)-free graphs. On the other hand, the complexity status for larger \(t\) is still unknown. In this paper we present a subexponential algorithm for the maximum (weighted) Independent set problem in \(P_t\)-free graphs.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alekseev, V., The effect of local constraints on the complexity of determination of the graph independence number, (Combinatorial-Algebraic Methods in Applied Mathematics (1982), Gorkiy University Press: Gorkiy University Press Gorky), 3-13, (in Russian)
[2] Alekseev, V., Polynomial algorithm for finding the largest independent sets in graphs without forks, Discrete Appl. Math., 135, 3-16 (2004), Russian Translations II
[3] Garey, M.; Johnson, D., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman · Zbl 0411.68039
[4] Impagliazzo, R.; Paturi, R., On the complexity of k-SAT, J. Comput. System Sci., 62, 367-375 (2001) · Zbl 0990.68079
[5] Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity?, J. Comput. System Sci., 63, 512-530 (2001) · Zbl 1006.68052
[8] Lozin, V. V.; Rautenbach, D., Some results on graphs without long induced paths, Inform. Process. Lett., 88, 167-171 (2003) · Zbl 1178.68285
[9] Mosca, R., Stable sets in certain \(P_6\)-free graphs, Discrete Appl. Math., 92, 177-191 (1999) · Zbl 0929.05076
[10] Randerath, B.; Schiermeyer, I., On maximum independent sets in \(P_5\)-free graphs, Discrete Appl. Math., 158, 1041-1044 (2010) · Zbl 1210.05164
[11] Rudin, W., (Principles of Mathematical Analysis. Principles of Mathematical Analysis, International Series in Pure & Applied Mathematics (1976), McGraw-Hill) · Zbl 0346.26002
[12] van’t Hof, P.; Paulusma, D., A new characterization of \(P_6\)-free graphs, Discrete Appl. Math., 158, 731-740 (2010) · Zbl 1225.05145
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.