Maximal independent set

Given a Graph G(V,E), it is easy to find a single MIS using the following algorithm:

1. Initialize I to an empty set.
2. While V is not empty:
   • Choose a node v∈V;
   • Add v to the set I;
   • Remove from V the node v and all its neighbours.
3. Return I.

The following algorithm finds a MIS in time O(log n).[1][7][8]

1. Initialize I to an empty set.
2. While V is not empty:
   • Choose a random set of vertices S ⊆ V, by selecting each vertex v independently with probability 1/(2d(v)), where d is the degree of v (the number of neighbours of v).
   • For every edge in E, if both its endpoints are in the random set S, then remove from S the endpoint whose degree is lower (i.e. has fewer neighbours). Break ties arbitrarily, e.g. using a lexicographic order on the vertex names.
   • Add the set S to I.
   • Remove from V the set S and all the neighbours of nodes in S.
3. Return I.

ANALYSIS: For each node v, divide its neighbours to lower neighbours (whose degree is lower than the degree of v) and higher neighbours (whose degree is higher than the degree of v), breaking ties as in the algorithm.

Call a node v bad if more than 2/3 of its neighbors are higher neighbours. Call an edge bad if both its endpoints are bad; otherwise the edge is good.

• At least 1/2 of all edges are always good. PROOF: Build a directed version of G by directing each edge to the node with the higher degree (breaking ties arbitrarily). So for every bad node, the number of out-going edges is more than 2 times the number of in-coming edges. So every bad edge, that enters a node v, can be matched to a distinct set of two edges that exit the node v. Hence the total number of edges is at least 2 times the number of bad edges.
• For every good node u, the probability that a neighbour of u is selected to S is at least a certain positive constant. PROOF: the probability that NO neighbour of u is selected to S is at most the probability that none of u's lower neighbours is selected. For each lower-neighbour v, the probability that it is not selected is (1-1/2d(v)), which is at most (1-1/2d(u)) (since d(u)>d(v)). The number of such neighbours is at least d(u)/3, since u is good. Hence the probability that no lower-neighbour is selected is at most 1-exp(-1/6).
• For every node u that is selected to S, the probability that u will be removed from S is at most 1/2. PROOF: This probability is at most the probability that a higher-neighbour of u is selected to S. For each higher-neighbour v, the probability that it is selected is at most 1/2d(v), which is at most 1/2d(u) (since d(v)>d(u)). By union bound, the probability that no higher-neighbour is selected is at most d(u)/2d(u) = 1/2.
• Hence, for every good node u, the probability that a neighbour of u is selected to S and remains in S is a certain positive constant. Hence, the probability that u is removed, in each step, is at least a positive constant.
• Hence, for every good edge e, the probability that e is removed, in each step, is at least a positive constant. So the number of good edges drops by at least a constant factor each step.
• Since at least half the edges are good, the total number of edges also drops by a constant factor each step.
• Hence, the number of steps is O(log m), where m is the number of edges. This is bounded by ${\displaystyle O(\log(n))}$.

A worst-case graph, in which the average number of steps is ${\displaystyle \Theta (\log(n))}$, is a graph made of n/2 connected components, each with 2 nodes. The degree of all nodes is 1, so each node is selected with probability 1/2, and with probability 1/4 both nodes in a component are not chosen. Hence, the number of nodes drops by a factor of 4 each step, and the expected number of steps is ${\displaystyle \log _{4}(n)}$.

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]

1. Initialize I to an empty set.
2. While V is not empty, each node v does the following:
   • Selects a random number r(v) in [0,1] and sends it to its neighbours;
   • If r(v) is smaller than the numbers of all neighbours of v, then v inserts itself into I, removes itself from V and tells its neighbours about this;
   • If v heard that one of its neighbours got into I, then v removes itself from V.
3. Return I.

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:

• A node ${\displaystyle v}$ has probability at least ${\displaystyle {\frac {1}{d(v)+d(w)}}}$ of being removed. PROOF: For each edge connecting a pair of nodes ${\displaystyle (v,w)}$, replace it with two directed edges, one from ${\displaystyle (v,w)}$ and the other ${\displaystyle (w,v)}$. Notice that ${\displaystyle |E|}$ is now twice as large. For every pair of directed edges ${\displaystyle (v,w)}$, define two events: ${\displaystyle (v\rightarrow w)}$ and ${\displaystyle (w\rightarrow v)}$, ${\displaystyle v}$ pre-emptively removes ${\displaystyle w}$ and ${\displaystyle w}$ pre-emptively removes ${\displaystyle v}$, respectively. The event ${\displaystyle (v\rightarrow w)}$ occurs when ${\displaystyle r(v)<r(w)}$ and ${\displaystyle r(v)<r(x)}$, where ${\displaystyle w}$ is a neighbor of ${\displaystyle v}$ and ${\displaystyle x}$ is neighbor ${\displaystyle w}$. Recall that each node is given a random number in the same [0, 1] range. In a simple example with two disjoint nodes, each has probability ${\displaystyle {\frac {1}{2}}}$ of being smallest. If there are three disjoint nodes, each has probability ${\displaystyle {\frac {1}{3}}}$ of being smallest. In the case of ${\displaystyle v}$, it has probability at least ${\displaystyle {\frac {1}{d(v)+d(w)}}}$ of being smallest because it is possible that a neighbor of ${\displaystyle v}$ is also the neighbor of ${\displaystyle w}$, so a node becomes double counted. Using the same logic, the event ${\displaystyle (w\rightarrow v)}$ also has probability at least ${\displaystyle {\frac {1}{d(w)+d(v)}}}$ of being removed.
• When the events ${\displaystyle (v\rightarrow w)}$ and ${\displaystyle (w\rightarrow v)}$ occur, they remove ${\displaystyle d(w)}$ and ${\displaystyle d(v)}$ directed outgoing edges, respectively. PROOF: In the event ${\displaystyle (v\rightarrow w)}$, when ${\displaystyle v}$ is removed, all neighboring nodes ${\displaystyle w}$ are also removed. The number of outgoing directed edges from ${\displaystyle w}$ removed is ${\displaystyle d(w)}$. With the same logic, ${\displaystyle (w\rightarrow v)}$ removes ${\displaystyle d(v)}$ directed outgoing edges.
• In each iteration of step 2, in expectation, half the edges are removed. PROOF: If the event ${\displaystyle (v\rightarrow w)}$ happens then all neighbours of ${\displaystyle w}$ are removed; hence the expected number of edges removed due to this event is at least ${\displaystyle {\frac {d(w)}{d(v)+d(w)}}}$. The same is true for the reverse event ${\displaystyle (w\rightarrow v)}$, i.e. the expected number of edges removed is at least ${\displaystyle {\frac {d(v)}{d(w)+d(v)}}}$. Hence, for every undirected edge ${\displaystyle (w,v)}$, the expected number of edges removed due to one of these nodes having smallest value is ${\displaystyle {\frac {d(w)+d(v)}{d(w)+d(v)}}=1}$. Summing over all edges, ${\displaystyle \sum _{{v,w}\in E}1=|E|}$, gives an expected number of ${\displaystyle |E|}$ edges removed every step, but each edge is counted twice (once per direction), giving ${\displaystyle {\frac {|E|}{2}}}$ edges removed in expectation every step.
• Hence, the expected run time of the algorithm is ${\displaystyle 3\log _{4/3}(m)+1}$ which is ${\displaystyle O(\log(n))}$.[8]

Instead of randomizing in each step, it is possible to randomize once, at the beginning of the algorithm, by fixing a random ordering on the nodes. Given this fixed ordering, the following parallel algorithm achieves exactly the same MIS as the #Sequential algorithm (i.e. the result is deterministic):[10]

1. Initialize I to an empty set.
2. While V is not empty:
   • Let W be the set of vertices in V with no earlier neighbours (based on the fixed ordering);
   • Add W to I;
   • Remove from V the nodes in the set W and all their neighbours.
3. Return I.

Between the totally sequential and the totally parallel algorithms, there is a continuum of algorithms that are partly sequential and partly parallel. Given a fixed ordering on the nodes and a factor δ∈(0,1], the following algorithm returns the same MIS:

1. Initialize I to an empty set.
2. While V is not empty:
   • Select a factor δ∈(0,1].
   • Let P be the set of δn nodes that are first in the fixed ordering.
   • Let W be a MIS on P using the totally parallel algorithm.
   • Add W to I;
   • Remove from V all the nodes in the prefix P, and all the neighbours of nodes in the set W.
3. Return I.

Setting δ=1/n gives the totally sequential algorithm; setting δ=1 gives the totally parallel algorithm.

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). Hence the total run-time of the partially parallel algorithm is ${\displaystyle O(\log ^{2}(n))}$. Hence the run-time of the fully parallel algorithm is also at most ${\displaystyle O(\log ^{2}(n))}$. The main proof steps are:

• If, in step i, we select ${\displaystyle \delta =2^{i}\log {(n)}/D}$, where D is the maximum degree of a node in the graph, then WHP all nodes remaining after step i have degree at most ${\displaystyle D/2^{i}}$. Thus, after log(D) steps, all remaining nodes have degree 0 (since D<n), and can be removed in a single step.
• If, in any step, the degree of each node is at most d, and we select ${\displaystyle \delta =C\log {(n)}/d}$ (for any constant C), then WHP the longest path in the directed graph determined by the fixed ordering has length ${\displaystyle O(\log(n))}$. Hence the fully parallel algorithm takes at most ${\displaystyle O(\log(n))}$ steps (since the longest path is a worst-case bound on the number of steps in that algorithm).
• Combining these two facts gives that, if we select ${\displaystyle \delta =2^{i}\log {(n)}/D}$, then WHP the run-time of the partially parallel algorithm is ${\displaystyle O(\log(D)\log(n))=O(\log ^{2}(n))}$.

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 ${\displaystyle NC^{1}}$ reduction from either the maximum set packing or the maximal matching problem or by an ${\displaystyle NC^{2}}$ reduction from the 2-satisfiability problem.[15][16] Typically, the structure of the algorithm given follows other parallel graph algorithms - that is they subdivide the graph into smaller local problems that are solvable in parallel by running an identical algorithm.

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 ${\displaystyle NC_{4}}$.[17] That is to say, their algorithm finds a maximal independent set in ${\displaystyle O(\log ^{4}n)}$ using ${\displaystyle O((n/\log n)^{3})}$, where ${\displaystyle n}$ is the vertex set size. In the same paper, a randomized parallel solution was also provided with a runtime of ${\displaystyle O(\log ^{4}n)}$ using ${\displaystyle O(n^{2})}$ processors. Shortly after, Luby and Alon et al. independently improved on this result, bringing the maximal independent set problem into the realm of ${\displaystyle NC_{2}}$ with an ${\displaystyle O(\log ^{2}n)}$ runtime using ${\displaystyle O(mn^{2})}$ processors, where ${\displaystyle m}$ is the number of edges in the graph.[16][7][18] In order to show that their algorithm is in ${\displaystyle NC_{2}}$, they initially presented a randomized algorithm that uses ${\displaystyle O(m)}$ processors but could be derandomized with an additional ${\displaystyle O(n^{2})}$ processors. Today, it remains an open question as to if the maximal independent set problem is in ${\displaystyle NC_{1}}$.

Distributed maximal independent set algorithms are strongly influenced by algorithms on the PRAM model. The original work by Luby and Alon et al. has led to several distributed algorithms.[19][20][21][18] In terms of exchange of bits, these algorithms had a message size lower bound per round of ${\displaystyle O(\log n)}$ bits and would require additional characteristics of the graph. 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 ${\displaystyle O(1)}$, which is optimal and removed the need for any additional graph knowledge.[22]