Maximal independent set
For example, in the graph P3, 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.
A graph may have many MISs of widely varying sizes;[a] the largest, or possibly several equally large, MISs of a graph is called a maximum independent set.
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.
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.
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 hard-sphere lattice gas model, a mathematical abstraction of fluid-solid state transitions.
A graph is said to be maximal-clique irreducible if every maximal clique has an edge that belongs to no other maximal clique, and hereditary maximal-clique irreducible if the same property is true for every induced subgraph.
Moon & Moser (1965) showed that any graph with n vertices has at most 3n/3 maximal cliques.
Any maximal independent set in this graph is formed by choosing one vertex from each triangle.
The following algorithm is better than the previous one in that at least one new node is always added in each connected component:[9][8] Note that in every step, the node with the smallest number in each connected component always enters I, so there is always some progress.
In particular, in the worst-case of the previous algorithm (n/2 connected components with 2 nodes each), a MIS will be found in a single step.
ANALYSIS: With a proper selection of the parameter δ in the partially parallel algorithm, it is possible to guarantee that it finishes after at most log(n) calls to the fully parallel algorithm, and the number of steps in each call is at most log(n).
The main proof steps are: An algorithm for listing all maximal independent sets or maximal cliques in a graph can be used as a subroutine for solving many NP-complete graph problems.
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 3-colorings of graphs: a graph can be 3-colored if and only if the complement of one of its maximal independent sets is bipartite.
[11] Other more complex problems can also be modeled as finding a clique or independent set of a specific type.
However, an algorithm with this time bound can be highly inefficient for graphs with more limited numbers of independent sets.
[14] The counting problem associated to maximal independent sets has been investigated in computational complexity theory.
The problem asks, given an undirected graph, how many maximal independent sets it contains.
[16] The maximal independent set problem was originally thought to be non-trivial to parallelize due to the fact that the lexicographical maximal independent set proved to be P-Complete; however, it has been shown that a deterministic parallel solution could be given by an
reduction from either the maximum set packing or the maximal matching problem or by an
Initial research into the maximal independent set problem started on the PRAM model and has since expanded to produce results for distributed algorithms on computer clusters.
The many challenges of designing distributed parallel algorithms apply in equal to the maximum independent set problem.
In particular, finding an algorithm that exhibits efficient runtime and is optimal in data communication for subdividing the graph and merging the independent set.
It was shown in 1984 by Karp et al. that a deterministic parallel solution on PRAM to the maximal independent set belonged in the Nick's Class complexity zoo of
Today, it remains an open question as to if the maximal independent set problem is in
The original work by Luby and Alon et al. has led to several distributed algorithms.
[21][22][23][20] In terms of exchange of bits, these algorithms had a message size lower bound per round of
For example, the size of the graph would need to be known or the maximum degree of neighboring vertices for a given vertex could be queried.
In 2010, Métivier et al. reduced the required message size per round to
