Extending the MAX Algorithm for Maximum Independent Set

• Autorzy: Ngoc C. Lê , Christoph Brause , Ingo Schiermeyer
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

maximum independent set; stable set; stability number; independence number; reduction; graph transformation; MAX Algorithm; MIN Algorithm; Vertex Order Algorithm

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 2
• Strony: 365-386

Daty

wydano

2015-05-01

otrzymano

2014-01-31

poprawiono

2015-01-07

zaakceptowano

2015-01-07

online

2015-04-18

Twórcy

autor

Ngoc C. Lê

• School of Applied Mathematics and Informatics Hanoi University of Science and Technology
• Faculty of Mathematics and Computer Science Technische Universität Bergakademie Freiberg

autor

Christoph Brause

• Faculty of Mathematics and Computer Science Technische Universität Bergakademie Freiberg

autor

Ingo Schiermeyer

• Faculty of Mathematics and Computer Science Technische Universität Bergakademie Freiberg

Bibliografia

• [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]
• [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]
• [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.
• [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]
• [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]
• [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]
• [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]
• [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]
• [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.
• [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.
• [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]
• [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]
• [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-#[Crossref]
• [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]
• [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[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]
• [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[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]

Identyfikatory

DOI

10.7151/dmgt.1811