Extending the MAX Algorithm for Maximum Independent Set

Ngoc C. Lê; Christoph Brause; Ingo Schiermeyer

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 2, page 365-386
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Ngoc C. Lê, Christoph Brause, and Ingo Schiermeyer. "Extending the MAX Algorithm for Maximum Independent Set." Discussiones Mathematicae Graph Theory 35.2 (2015): 365-386. <http://eudml.org/doc/271095>.

@article{NgocC2015,
abstract = {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.},
author = {Ngoc C. Lê, Christoph Brause, Ingo Schiermeyer},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {maximum independent set; stable set; stability number; independence number; reduction; graph transformation; MAX Algorithm; MIN Algorithm; Vertex Order Algorithm; MAX algorithm; MIN algorithm; vertex order algorithm},
language = {eng},
number = {2},
pages = {365-386},
title = {Extending the MAX Algorithm for Maximum Independent Set},
url = {http://eudml.org/doc/271095},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Ngoc C. Lê
AU - Christoph Brause
AU - Ingo Schiermeyer
TI - Extending the MAX Algorithm for Maximum Independent Set
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 2
SP - 365
EP - 386
AB - 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.
LA - eng
KW - maximum independent set; stable set; stability number; independence number; reduction; graph transformation; MAX Algorithm; MIN Algorithm; Vertex Order Algorithm; MAX algorithm; MIN algorithm; vertex order algorithm
UR - http://eudml.org/doc/271095
ER -

References

top
  1. [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. [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. [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] Zbl1056.05131
  4. [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. [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] Zbl0968.05058
  6. [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. [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. Zbl0588.05020
  8. [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] Zbl1017.68087
  9. [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] Zbl0463.05057
  10. [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] Zbl0575.68065
  11. [11] C. Ebenegger, P.L. Hammer and D. Werra, Pseudo-Boolean functions and stability of graphs, Ann. Discrete Math. 19 (1984) 83-98. 
  12. [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] Zbl1029.68115
  13. [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. [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] Zbl0651.68083
  15. [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. [16] P.L. Hammer and A. Hertz, On a transformation which preserves the stability number( RUTCOR Research report, Rutgers University1991) 69-91. 
  17. [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. [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. [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. Zbl1080.05067
  20. [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. [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. [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. [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. Zbl1302.05134
  24. [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] Zbl1159.05313
  25. [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] Zbl1189.05136
  26. [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. Zbl06247338
  27. [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] Zbl0918.05086
  28. [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] Zbl0434.05043
  29. [29] R. Mosca, Independent sets in (P6,diamond)-free graphs, Discrete Math. Theor. Comput. Sci. 11 (2009) 125-140. Zbl1196.05065
  30. [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. [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. [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. [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] Zbl0353.65019
  34. [34] N. Sbihi, Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile, Discrete Math. 29 (1980) 53-76. Zbl0444.05049
  35. [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. [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] Zbl1057.05063

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.