The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.
@article{bwmeta1.element.doi-10_7151_dmgt_1811,
author = {Ngoc C. L\^e and Christoph Brause and Ingo Schiermeyer},
title = {Extending the MAX Algorithm for Maximum Independent Set},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {365-386},
zbl = {1311.05152},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1811}
}
Ngoc C. Lê; Christoph Brause; Ingo Schiermeyer. Extending the MAX Algorithm for Maximum Independent Set. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 365-386. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1811/
[1] V.E. Alekseev, On the ocal restrictions effect on the complexity of finding the graph independence number , in: Combinatorial-Algebraic Methods in Applied Mathematics, A. Markov (Ed(s)), (Gorkiy University, 1983) 3-13, in Russian.
[2] V.E. Alekseev, A polynomial algorithm for finding maximum independent sets in fork-free graphs, Discrete Anal. Operation Research Serie 1 6(4) (1999) 3-19, in Russian.
[3] V.E. Alekseev, Augmenting graphs for independent sets, Discrete Appl. Math. 145 (2004) 3-10. doi:10.1016/j.dam.2003.09.003[Crossref] | Zbl 1056.05131
[4] A. Billionnet, Reductions and optimality conditions in the problem of a maximum weighted stable set , RAIRO Recherche Opérationnelle 15(3) (1999) 213-231, in French.
[5] A. Brandstädt and V.V. Lozin, A note on -redundant vertices in graphs, Discrete Appl. Math. 108 (2001) 301-308. doi:10.1016/S0166-218X(00)00239-0[Crossref] | Zbl 0968.05058
[6] A. Brandstädt, H.O. Le, V.B. Le, On -redundant vertices in P5-free graphs, Inform. Process. Lett. 82 (2002) 119-122. doi:10.1016/S0020-0190(01)00265-4[Crossref]
[7] L. Butz, P.L. Hammer and D. Haussmann, Reduction methods for the vertex packing problem, in: Proceedings of the 17th Conference on Probability Theory, Brasov, Romania, 1982, M. Iosifescu, T. Postelnicu, S. Grigorescu (Ed(s)), (Utrecht, VNU Science Press, 1985) 73-79. | Zbl 0588.05020
[8] J. Chen, I.A. Kanji and W. Jia, Vertex cover: further observations and further improvement , J. Algorithms 41 (2001) 280-301. doi:10.1006/jagm.2001.1186[Crossref] | Zbl 1017.68087
[9] D.G. Corneil, H. Lerchs and L.S. Burlingham, Complement reducible graphs, Discrete Appl. Math. 3 (1981) 163-174. doi:10.1016/0166-218X(81)90013-5[Crossref] | Zbl 0463.05057
[10] D.G. Corneil, Y. Perl and L.K. Stewart, A linear recognition algorithm for cographs, SIAM J. Comput. 14 (1985) 926-934. doi:10.1137/0214065[Crossref] | Zbl 0575.68065
[11] C. Ebenegger, P.L. Hammer and D. Werra, Pseudo-Boolean functions and stability of graphs, Ann. Discrete Math. 19 (1984) 83-98.
[12] M.U. Gerber and V.V. Lozin, Robust algorithms for the stable set problem, Graphs Combin. 19 (2003) 347-356. doi:10.1007/s00373-002-0517-5[Crossref] | Zbl 1029.68115
[13] M.U. Gerber and V.V. Lozin, On the stable set problem in special P5-free graphs, Discrete Appl. Math. 125 (2003) 215-224. doi:10.1016/S0166-218X(01)00321-3[Crossref]
[14] M.C. Golumbic and P.L. Hammer, Stability in circular arc graphs, J. Algorithms 9 (1988) 314-320. doi:10.1016/0196-6774(88)90023-5[Crossref] | Zbl 0651.68083
[15] J.R. Griggs, Lower bounds on the independence number in terms of the degree, J. Combin. Theory (B) 34 (1983) 22-39. doi:10.1016/0095-8956(83)90003-5[Crossref]
[16] P.L. Hammer and A. Hertz, On a transformation which preserves the stability number( RUTCOR Research report, Rutgers University1991) 69-91.
[17] J. Harant, Z. Ryjáček and I. Schiermeyer, Forbidden subgraphs implying the MINalgorithm gives a maximum independent set , Discrete Math. 256 (2002) 193-201. doi:10.1016/S0012-365X(02)00571-X[Crossref]
[18] A. Hertz, On the use Boolean methods for the computation of the stability number , Discrete Appl. Math. 76 (1997) 183-203. doi:10.1016/S0166-218X(96)00124-2[Crossref]
[19] A. Hertz and V.V. Lozin, The maximum independent set problem and augmenting graphs, in: Graph Theory Combin. Optim., D. Avis, A. Hertz, O. Marcotte (Ed(s)), (Springer, 2005) 69-99. | Zbl 1080.05067
[20] N.C. Lê, C. Brause and I. Schiermeyer, New sufficient conditions for -redundant vertices, Discrete Math. (2014) in press. doi:10.1016/j.disc.2014.07.002[Crossref]
[21] D. Lokshtanov, M. Vatshelle and Y. Villanger, Independent set in P5-free graphs in polynomial time, Technical Report (2013). www.ii.uib.no/~martinv/Papers/ISinP5free.pdf
[22] V.V. Lozin and D. Rautenbach, Some results on graphs without long induced paths, Inform. Process. Lett. 88 (2004) 167-171. doi:10.1016/j.ipl.2003.07.004 [Crossref]
[23] V.V. Lozin and M. Milanič, Maximum independent sets in graphs of low degree, in: Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms SoDA’ 07, H. Gabow (Ed(s)), (Society for Industrial and Applied Mathematics, 2007) 874-880. | Zbl 1302.05134
[24] V.V. Lozin and M. Milanič, On finding augmenting graphs, Discrete Appl. Math. 156 (2008) 2517-2529. doi:10.1016/j.dam.2008.03.008[Crossref] | Zbl 1159.05313
[25] V.V. Lozin and R.Mosca, Maximum independent sets in subclasses of P5-free graphs, Inform. Process. Lett. 109 (2009) 319-324. doi:10.1016/j.ipl.2008.11.005[Crossref] | Zbl 1189.05136
[26] V.V. Lozin, J. Monnot and B. Ries, On the maximum independent set problem in subclasses of subcubic graphs, in: International Workshop on Combinatorial Algorithms IWOCA 2013, T. Lecroq, L. Mouchard (Ed(s)), (Springer, 2013) 314-326. | Zbl 06247338
[27] N.V.R. Mahadev and B.A. Reed, A note on vertex orders for stability number , J. Graph Theory 30 (1999) 113-120. doi:10.1002/(SICI)1097-0118(199902)30:2h113::AID-JGT5i3.0.CO;2-#[Crossref] | Zbl 0918.05086
[28] G.J. Minty, On maximal independent sets of vertices in claw-free graphs, J. Combin. Theory (B) 28 (1980) 284-304. doi:10.1016/0095-8956(80)90074-X[Crossref] | Zbl 0434.05043
[29] R. Mosca, Independent sets in (P6,diamond)-free graphs, Discrete Math. Theor. Comput. Sci. 11 (2009) 125-140. | Zbl 1196.05065
[30] R. Mosca, Stable sets for (P6,K2 , 3)-free graphs, Discuss. Math. Graph Theory 32 (2012) 387-401. doi:10.7151/dmgt.1598[Crossref][WoS]
[31] O.J. Murphy, Lower bounds on the stability number of graphs computed in terms of degrees, Discrete Math. 90 (1991) 207-211. doi:10.1016/0012-365X(91)90357-8[Crossref]
[32] O.J. Murphy, Computing independent sets in graphs with large girth, Discrete Appl. Math. 35 (1992) 167-170. doi:0.1016/0166-218X(92)90041-8
[33] D.J. Rose, R.E. Tarjan and G.S. Lueker, Algorithmic aspects of vertex elimination of graphs, SIAM J. Comput. 5 (1976) 266-283. doi:10.1137/0205021[Crossref] | Zbl 0353.65019
[34] N. Sbihi, Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile, Discrete Math. 29 (1980) 53-76. | Zbl 0444.05049
[35] I.E. Zverovich, Minimum degree algorithms for stability number , Discrete Appl. Math. 132 (2004) 211-216. doi:10.1016/0012-365X(90)90287-R[Crossref]
[36] I.E. Zverovich and O.I. Zverovich, Stability number in subclasses of P5-free graphs, Appl. Math. J. Chinese Univ. Ser. B 19 (2004) 125-132. doi:10.1007/s11766-004-0045-6 [Crossref] | Zbl 1057.05063