Years and Authors of Summarized Original Work
-
1977; Tarjan, Trojanowski
-
1985; Robson
-
1999; Beigel
-
2009; Fomin, Grandoni, Kratsch
Problem Definition
Let G = (V, E) be an n-node undirected, simple graph without loops. A set I ⊆ V is called an independent set of G if the nodes of I are pairwise not adjacent. The maximum independent set (MIS) problem asks to determine the maximum cardinality α(G) of an independent set of G. MIS is one of the best studied NP-hard problems.
We will need the following notation. The (open) neighborhood of a vertex v is N(v) = { u ∈ V : uv ∈ E}, and its closed neighborhood is N[v] = N(v) ∪{ v}. The degree deg(v) of v is | N(v) | . For W ⊆ V, \(G[W] = (W,E \cap \binom{W}{2})\) is the graph induced by W. We let \(G - W = G[V - W]\).
Key Results
A very simple algorithm solves MIS (exactly) in O∗(2n) time: it is sufficient to enumerate all the subsets of nodes, check in polynomial time whether each subset is an independent set or not, and return the maximum...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Beigel R (1999) Finding maximum independent sets in sparse and general graphs. In: ACM-SIAM symposium on discrete algorithms (SODA), Baltimore, pp 856–857
Bourgeois N, Escoffier B, Paschos VT, van Rooij JMM (2012) Fast algorithms for max independent set. Algorithmica 62(1–2):382–415
Fomin FV, Grandoni F, Kratsch D (2009) A measure & conquer approach for the analysis of exact algorithms. J ACM 56(5):Article no. 25
Fürer M (2006) A faster algorithm for finding maximum independent sets in sparse graphs. In: Latin American theoretical informatics symposium (LATIN), Valdivia, pp 491–501
Kneis J, Langer A, Rossmanith P (2009) A fine-grained analysis of a simple independent set algorithm. In: Foundations of software technology and theoretical computer science (FSTTCS), Kanpur, pp 287–298
Robson JM (1986) Algorithms for maximum independent sets. J Algorithms 7(3):425–440
Tarjan R, Trojanowski A (1977) Finding a maximum independent set. SIAM J Comput 6(3):537–546
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer Science+Business Media New York
About this entry
Cite this entry
Grandoni, F. (2016). Exact Algorithms for Maximum Independent Set. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_514
Download citation
DOI: https://doi.org/10.1007/978-1-4939-2864-4_514
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4939-2863-7
Online ISBN: 978-1-4939-2864-4
eBook Packages: Computer ScienceReference Module Computer Science and Engineering