Geodesic
Extending the MAX Algorithm for Maximum Independent Set
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 365-386.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: maximum independent set, stable set, stability number, independence number, reduction, graph transformation, MAX Algorithm, MIN Algorithm, Vertex Order Algorithm 
@article{DMGT_2015_35_2_a13,
     author = {L\^e, Ngoc C. and Brause, Christoph and Schiermeyer, Ingo},
     title = {Extending the {MAX} {Algorithm} for {Maximum} {Independent} {Set}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {365--386},
     publisher = {mathdoc},
     volume = {35},
     number = {2},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a13/}
}
TY  - JOUR
AU  - Lê, Ngoc C.
AU  - Brause, Christoph
AU  - Schiermeyer, Ingo
TI  - Extending the MAX Algorithm for Maximum Independent Set
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 365
EP  - 386
VL  - 35
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a13/
LA  - en
ID  - DMGT_2015_35_2_a13
ER  - 
%0 Journal Article
%A Lê, Ngoc C.
%A Brause, Christoph
%A Schiermeyer, Ingo
%T Extending the MAX Algorithm for Maximum Independent Set
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 365-386
%V 35
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a13/
%G en
%F DMGT_2015_35_2_a13
Lê, Ngoc C.; Brause, Christoph; Schiermeyer, Ingo. Extending the MAX Algorithm for Maximum Independent Set. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 365-386. http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a13/

[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

[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

[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

[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.

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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.

[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

[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

[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.

[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

[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

[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.

[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-#

[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

[29] R. Mosca, Independent sets in (P6,diamond)-free graphs, Discrete Math. Theor. Comput. Sci. 11 (2009) 125-140.

[30] R. Mosca, Stable sets for (P6,K2, 3)-free graphs, Discuss. Math. Graph Theory 32 (2012) 387-401. doi:10.7151/dmgt.1598

[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

[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

[34] N. Sbihi, Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile, Discrete Math. 29 (1980) 53-76.

[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

[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