 Maximal independent set

This article is about the combinatorial aspects of maximal independent sets of vertices in a graph. For other aspects of independent vertex sets in graph theory, see Independent set (graph theory). For other kinds of independent sets, see Independent set (disambiguation).
In graph theory, a maximal independent set or maximal stable set is an independent set that is not a subset of any other independent set. That is, it is a set S such that every edge of the graph has at least one endpoint not in S and every vertex not in S has at least one neighbor in S. A maximal independent set is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so maximal independent sets are also called independent dominating sets. A graph may have many maximal independent sets of widely varying sizes;^{[1]} a largest maximal independent set is called a maximum independent set.
For example, in the graph P_{3}, a path with three vertices a, b, and c, and two edges ab and bc, the sets {b} and {a,c} are both maximally independent. The set {a} is independent, but is not maximal independent, because it is a subset of the larger independent set {a,c}. In this same graph, the maximal cliques are the sets {a,b} and {b,c}.
The phrase "maximal independent set" is also used to describe maximal subsets of independent elements in mathematical structures other than graphs, and in particular in vector spaces and matroids.
Contents
Related vertex sets
If S is a maximal independent set in some graph, it is a maximal clique or maximal complete subgraph in the complementary graph. A maximal clique is a set of vertices that induces a complete subgraph, and that is not a subset of the vertices of any larger complete subgraph. That is, it is a set S such that every pair of vertices in S is connected by an edge and every vertex not in S is missing an edge to at least one vertex in S. A graph may have many maximal cliques, of varying sizes; finding the largest of these is the maximum clique problem.
Some authors include maximality as part of the definition of a clique, and refer to maximal cliques simply as cliques.
The complement of a maximal independent set, that is, the set of vertices not belonging to the independent set, forms a minimal vertex cover. That is, the complement is a vertex cover, a set of vertices that includes at least one endpoint of each edge, and is minimal in the sense that none of its vertices can be removed while preserving the property that it is a cover. Minimal vertex covers have been studied in statistical mechanics in connection with the hardsphere lattice gas model, a mathematical abstraction of fluidsolid state transitions.^{[2]}
Every maximal independent set is a dominating set, a set of vertices such that every vertex in the graph either belongs to the set or is adjacent to the set. A set of vertices is a maximal independent set if and only if it is an independent dominating set.
Graph family characterizations
Certain graph families have also been characterized in terms of their maximal cliques or maximal independent sets. Examples include the maximalclique irreducible and hereditary maximalclique irreducible graphs. A graph is said to be maximalclique irreducible if every maximal clique has an edge that belongs to no other maximal clique, and hereditary maximalclique irreducible if the same property is true for every induced subgraph.^{[3]} Hereditary maximalclique irreducible graphs include trianglefree graphs, bipartite graphs, and interval graphs.
Cographs can be characterized as graphs in which every maximal clique intersects every maximal independent set, and in which the same property is true in all induced subgraphs.
Bounding the number of sets
Moon & Moser (1965) showed that any graph with n vertices has at most 3^{n/3} maximal cliques. Complementarily, any graph with n vertices also has at most 3^{n/3} maximal independent sets. A graph with exactly 3^{n/3} maximal independent sets is easy to construct: simply take the disjoint union of n/3 triangle graphs. Any maximal independent set in this graph is formed by choosing one vertex from each triangle. The complementary graph, with exactly 3^{n/3} maximal cliques, is a special type of Turán graph; because of their connection with Moon and Moser's bound, these graphs are also sometimes called MoonMoser graphs. Tighter bounds are possible if one limits the size of the maximal independent sets: the number of maximal independent sets of size k in any nvertex graph is at most
The graphs achieving this bound are again Turán graphs.^{[4]}
Certain families of graphs may, however, have much more restrictive bounds on the numbers of maximal independent sets or maximal cliques. For instance, if all graphs in a family of graphs have O(n) edges, and the family is closed under subgraphs, then all maximal cliques have constant size and there can be at most linearly many maximal cliques.^{[5]}
Any maximalclique irreducible graph, clearly, has at most as many maximal cliques as it has edges. A tighter bound is possible for interval graphs, and more generally chordal graphs: in these graphs there can be at most n maximal cliques.
The number of maximal independent sets in nvertex cycle graphs is given by the Perrin numbers, and the number of maximal independent sets in nvertex path graphs is given by the Padovan sequence.^{[6]} Therefore, both numbers are proportional to powers of 1.324718, the plastic number.
Set listing algorithms
Further information: Clique problem#Listing all maximal cliquesAn algorithm for listing all maximal independent sets or maximal cliques in a graph can be used as a subroutine for solving many NPcomplete graph problems. Most obviously, the solutions to the maximum independent set problem, the maximum clique problem, and the minimum independent dominating problem must all be maximal independent sets or maximal cliques, and can be found by an algorithm that lists all maximal independent sets or maximal cliques and retains the ones with the largest or smallest size. Similarly, the minimum vertex cover can be found as the complement of one of the maximal independent sets. Lawler (1976) observed that listing maximal independent sets can also be used to find 3colorings of graphs: a graph can be 3colored if and only if the complement of one of its maximal independent sets is bipartite. He used this approach not only for 3coloring but as part of a more general graph coloring algorithm, and similar approaches to graph coloring have been refined by other authors since.^{[7]} Other more complex problems can also be modeled as finding a clique or independent set of a specific type. This motivates the algorithmic problem of listing all maximal independent sets (or equivalently, all maximal cliques) efficiently.
It is straightforward to turn a proof of Moon and Moser's 3^{n/3} bound on the number of maximal independent sets into an algorithm that lists all such sets in time O(3^{n/3}).^{[8]} For graphs that have the largest possible number of maximal independent sets, this algorithm takes constant time per output set. However, an algorithm with this time bound can be highly inefficient for graphs with more limited numbers of independent sets. For this reason, many researchers have studied algorithms that list all maximal independent sets in polynomial time per output set.^{[9]} The time per maximal independent set is proportional to that for matrix multiplication in dense graphs, or faster in various classes of sparse graphs.^{[10]}
Notes
 ^ Erdős (1966) shows that the number of different sizes of maximal independent sets in an nvertex graph may be as large as n  log n  O(log log n) and is never larger than n  log n.
 ^ Weigt & Hartmann (2001).
 ^ Information System on Graph Class Inclusions: maximal clique irreducible graphs and hereditary maximal clique irreducible graphs.
 ^ Byskov (2003). For related earlier results see Croitoru (1979) and Eppstein (2003).
 ^ Chiba & Nishizeki (1985). The sparseness condition is equivalent to assuming that the graph family has bounded arboricity.
 ^ Bisdorff & Marichal (2007); Euler (2005); Füredi (1987).
 ^ Eppstein (2003); Byskov (2003).
 ^ Eppstein (2003). For a matching bound for the widely used Bron–Kerbosch algorithm, see Tomita, Tanaka & Takahashi (2006).
 ^ Bomze et al. (1999); Eppstein (2005); Jennings & Motycková (1992); Johnson, Yannakakis & Papadimitriou (1988); Lawler, Lenstra & Rinnooy Kan (1980); Liang, Dhall & Lakshmivarahan (1991); Makino & Uno (2004); Mishra & Pitt (1997); Stix (2004); Tsukiyama et al. (1977); Yu & Chen (1993).
 ^ Makino & Uno (2004); Eppstein (2005).
References
 Bisdorff, R.; Marichal, J.L. (2007), Counting nonisomorphic maximal independent sets of the ncycle graph, arXiv:math.CO/0701647.
 Bomze, I. M.; Budinich, M.; Pardalos, P. M.; Pelillo, M. (1999), "The maximum clique problem", Handbook of Combinatorial Optimization, 4, Kluwer Academic Publishers, pp. 1–74, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.4074&rep=rep1&type=pdf.
 Byskov, J. M. (2003), "Algorithms for kcolouring and finding maximal independent sets", Proceedings of the Fourteenth Annual ACMSIAM Symposium on Discrete Algorithms, pp. 456–457, http://portal.acm.org/citation.cfm?id=644182.
 Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM J. on Computing 14 (1): 210–223, doi:10.1137/0214017.
 Croitoru, C. (1979), "On stables in graphs", Proc. Third Coll. Operations Research, BabeşBolyai University, ClujNapoca, Romania, pp. 55–60.
 Eppstein, D. (2003), "Small maximal independent sets and faster exact graph coloring", Journal of Graph Algorithms and Applications 7 (2): 131–140, arXiv:cs.DS/cs.DS/0011009, http://www.cs.brown.edu/publications/jgaa/accepted/2003/Eppstein2003.7.2.pdf.
 Eppstein, D. (2005), "All maximal independent sets and dynamic dominance for sparse graphs", Proc. Sixteenth Annual ACMSIAM Symposium on Discrete Algorithms, pp. 451–459, arXiv:cs.DS/0407036.
 Erdős, P. (1966), "On cliques in graphs", Israel J. Math. 4 (4): 233–234, doi:10.1007/BF02771637, MR0205874.
 Euler, R. (2005), "The Fibonacci number of a grid graph and a new class of integer sequences", Journal of Integer Sequences 8 (2): 05.2.6.
 Füredi, Z. (1987), "The number of maximal independent sets in connected graphs", Journal of Graph Theory 11 (4): 463–470, doi:10.1002/jgt.3190110403.
 Jennings, E.; Motycková, L. (1992), "A distributed algorithm for finding all maximal cliques in a network graph", Proc. First Latin American Symposium on Theoretical Informatics, Lecture Notes in Computer Science, 583, SpringerVerlag, pp. 281–293
 Johnson, D. S.; Yannakakis, M.; Papadimitriou, C. H. (1988), "On generating all maximal independent sets", Information Processing Letters 27 (3): 119–123, doi:10.1016/00200190(88)900658.
 Lawler, E. L. (1976), "A note on the complexity of the chromatic number problem", Information Processing Letters 5 (3): 66–67, doi:10.1016/00200190(76)90065X.
 Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G. (1980), "Generating all maximal independent sets: NPhardness and polynomial time algorithms", SIAM Journal on Computing 9 (3): 558–565, doi:10.1137/0209042.
 Leung, J. Y.T. (1984), "Fast algorithms for generating all maximal independent sets of interval, circulararc and chordal graphs", Journal of Algorithms 5: 22–35, doi:10.1016/01966774(84)900373.
 Liang, Y. D.; Dhall, S. K.; Lakshmivarahan, S. (1991), On the problem of finding all maximum weight independent sets in interval and circular arc graphs, pp. 465–470
 Makino, K.; Uno, T. (2004), New algorithms for enumerating all maximal cliques, Lecture Notes in Compute Science, 3111, SpringerVerlag, pp. 260–272, http://www.springerlink.com/content/p9qbl6y1v5t3xc1w/.
 Mishra, N.; Pitt, L. (1997), "Generating all maximal independent sets of boundeddegree hypergraphs", Proc. Tenth Conf. Computational Learning Theory, pp. 211–217, doi:10.1145/267460.267500, ISBN 0897918916.
 Moon, J. W.; Moser, L. (1965), "On cliques in graphs", Israel Journal of Mathematics 3: 23–28, doi:10.1007/BF02760024, MR0182577.
 Stix, V. (2004), "Finding all maximal cliques in dynamic graphs", Computational Optimization Appl. 27 (2): 173–186, doi:10.1023/B:COAP.0000008651.28952.b6
 Tomita, E.; Tanaka, A.; Takahashi, H. (2006), "The worstcase time complexity for generating all maximal cliques and computational experiments", Theoretical Computer Science 363 (1): 28–42, doi:10.1016/j.tcs.2006.06.015.
 Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Shirakawa, I. (1977), "A new algorithm for generating all the maximal independent sets", SIAM J. on Computing 6 (3): 505–517, doi:10.1137/0206036.
 Weigt, Martin; Hartmann, Alexander K. (2001), "Minimal vertex covers on finiteconnectivity random graphs: A hardsphere latticegas picture", Phys. Rev. E 63 (5): 056127, arXiv:condmat/0011446, doi:10.1103/PhysRevE.63.056127.
 Yu, C.W.; Chen, G.H. (1993), "Generate all maximal independent sets in permutation graphs", Internat. J. Comput. Math. 47: 1–8, doi:10.1080/00207169308804157.
Categories: Graph theory objects
 Computational problems in graph theory
Wikimedia Foundation. 2010.
Look at other dictionaries:
Independent set (graph theory) — The nine blue vertices form a maximum independent set for the Generalized Petersen graph GP(12,4). In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices … Wikipedia
Independent set — The (unexpectedly asymmetric) set of 9 blue vertices is a maximal independent set for this graph of 24 vertices.In graph theory, an independent set or stable set is a set of vertices in a graph no two of which are adjacent. That is, it is a set V … Wikipedia
Independent set problem — In mathematics, the independent set problem (IS) is a well known problem in graph theory and combinatorics. The independent set problem is known to be NP complete. It is almost identical to the clique problem. Description Given a graph G , an… … Wikipedia
Independent Set — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… … Deutsch Wikipedia
Dominating set — For Dominator in control flow graphs, see Dominator (graph theory). Dominating sets (red vertices). In graph theory, a dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is joined to at… … Wikipedia
Edge dominating set — Examples of edge dominating sets. In graph theory, an edge dominating set for a graph G = (V, E) is a subset D ⊆ E such that every edge not in D is adjacent to at least one edge in D. An edge dominating set is also known… … Wikipedia
Redundant Array of Independent Disks — Der Begriff RAID steht für englisch redundant array of independent disks (deutsch: Redundante Anordnung unabhängiger Festplatten, ursprünglich: redundant array of inexpensive disks, deutsch: Redundante Anordnung kostengünstiger Festplatten, was… … Deutsch Wikipedia
Tree (set theory) — In set theory, a tree is a partially ordered set (poset) ( T … Wikipedia
Matroid — In combinatorics, a branch of mathematics, a matroid ( /ˈmeɪ … Wikipedia
Split graph — In graph theory, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer in two papers in 1977, and independently introduced by Tyshkevich and… … Wikipedia