Maximum independent sets in graphs of low degree

ABSTRACT

We study computational complexity of the maximum independent set problem on graphs of bounded vertex degree. In general, this problem is NP-hard. However, under certain restrictions it becomes polynomial-time solvable. We identify three graph properties to which the complexity of the problem is sensible.

REFERENCES

• 1: V. E. Alekseev, On the number of maximal independent sets in graphs from hereditary classes, Combinatorial-algebraic methods in discrete optimization, University of Nizhny Novgorod, (1991) 5--8 (in Russian).
• 2: V. E. Alekseev, Polynomial algorithm for finding the largest independent sets in graphs without forks, Discrete Applied Mathematics, v.135 n.1-3, p.3-16, 15 January 2004 [doi>10.1016/S0166-218X(02)00290-1]
• 3: Stefan Arnborg , Jens Lagergren , Detlef Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, v.12 n.2, p.308-340, June 1991 [doi>10.1016/0196-6774(91)90006-K]
• 4: Hans L. Bodlaender , Dimitrios M. Thilikos, Treewidth for graphs with small chordality, Discrete Applied Mathematics, v.79 n.1-3, p.45-61, Nov. 27, 1997
• 5: A. Brandstädt, C. Hoàng, On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem, Proceedings IPCO 2005, Berlin, LNCS 3509, 265--275.
• 6: Hajo Broersma , Ton Kloks , Dieter Kratsch , Haiko Müller, Independent Sets in Asteroidal Triple-Free Graphs, SIAM Journal on Discrete Mathematics, v.12 n.2, p.276-287, 1999 [doi>10.1137/S0895480197326346]
• 7: M. Farber, M. Hujter and Zs. Tuza, An upper bound on the number of cliques in a graph, Networks 23 (1993) 207--210.
• 8: F. Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. Comput. 1 (1972) 180--187.
• 9: M. G. Garey and D. S. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM J. Appl. Math. 32 (1977) no. 4, 826--834.
• 10: M. Grötschel, L. Lovász and A. Schrijver, Polynomial algorithms for perfect graphs, Ann. Discrete Math. 21 (1984) 325--356.
• 11: A. Hertz , D. de Werra, On the stability number of AH-free graphs, Journal of Graph Theory, v.17 n.1, p.53-63, March 1993 [doi>10.1002/jgt.3190170107]
• 12: Vadim V. Lozin , Martin Milanič, A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.26-30, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109561]
• 13: G. J. Minty, On maximal independent sets of vertices in claw-free graphs, J. Combinatorial Theory, Ser. B, 28 (1980) 284--304.
• 14: Owen J. Murphy, Computing independent sets in graphs with large girth, Discrete Applied Mathematics, v.35 n.2, p.167-170, Jan. 9, 1992 [doi>10.1016/0166-218X(92)90041-8]
• 15: D. Nakamura and A. Tamura, A revision of Minty's algorithm for finding a maximum weight stable set of a claw-free graph, J. Oper. Res. Soc. Japan 44 (2001) 194--204.
• 16: E. Prisner, Graphs with few cliques, Graph theory, combinatorics, and algorithms, Vol. 1, 2 (Kalamazoo, MI, 1992), 945--956, Wiley-Intersci. Publ., Wiley, New York, 1995.
• 17: N. Sbihi, Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile, Discrete Math. 29 (1980) 53--76.
• 18: R. E. Tarjan, Decomposition by clique separators. Discrete Math., 55 (1985) 221--232.
• 19: S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirakawa, A new algorithm for generating all the maximal independent sets, SIAM J. Computing, 6 (1977) 505--517.

INDEX TERMS

Keywords:
NP-hardness, independent set, polynomial-time algorithm