Maximal independent set

Definition

2. where denotes the neighbors of

Related vertex sets

Graph family characterizations

Bounding the number of sets

Finding a single maximal independent set

Sequential algorithm

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

Random-selection parallel algorithm Luby's Algorithm

1. Initialize I to an empty set.
2. While V is not empty:
3. * Choose a random set of vertices S ⊆ V, by selecting each vertex v independently with probability 1/, where d is the degree of v.
4. * 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. Break ties arbitrarily, e.g. using a lexicographic order on the vertex names.
5. * Add the set S to I.
6. * Remove from V the set S and all the neighbours of nodes in S.
7. Return I.

• 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. 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, which is at most >d). The number of such neighbours is at least d/3, since u is good. Hence the probability that no lower-neighbour is selected is at most 1-exp.
• 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, which is at most 1/2d >d). By union bound, the probability that no higher-neighbour is selected is at most d/2d = 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, where m is the number of edges. This is bounded by.

Random-priority parallel algorithm

1. Initialize I to an empty set.
2. While V is not empty, each node v does the following:
3. * Selects a random number r in and sends it to its neighbours;
4. * If r 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;
5. * If v heard that one of its neighbours got into I, then v removes itself from V.
6. Return I.

• A node has probability at least of being removed. PROOF: For each edge connecting a pair of nodes, replace it with two directed edges, one from and the other. Notice that is now twice as large. For every pair of directed edges, define two events: and, pre-emptively removes and pre-emptively removes, respectively. The event occurs when and, where is a neighbor of and is neighbor. Recall that each node is given a random number in the same range. In a simple example with two disjoint nodes, each has probability of being smallest. If there are three disjoint nodes, each has probability of being smallest. In the case of, it has probability at least of being smallest because it is possible that a neighbor of is also the neighbor of, so a node becomes double counted. Using the same logic, the event also has probability at least of being removed.
• When the events and occur, they remove and directed outgoing edges, respectively. PROOF: In the event , when is removed, all neighboring nodes are also removed. The number of outgoing directed edges from removed is. With the same logic, removes directed outgoing edges.
• In each iteration of step 2, in expectation, half the edges are removed. PROOF: If the event happens then all neighbours of are removed; hence the expected number of edges removed due to this event is at least. The same is true for the reverse event, i.e. the expected number of edges removed is at least. Hence, for every undirected edge, the expected number of edges removed due to one of these nodes having smallest value is. Summing over all edges,, gives an expected number of edges removed every step, but each edge is counted twice, giving edges removed in expectation every step.
• Hence, the expected run time of the algorithm is which is.

  Random-permutation parallel algorithm Blelloch's Algorithm

1. Initialize I to an empty set.
2. While V is not empty:
3. * Let W be the set of vertices in V with no earlier neighbours ;
4. * Add W to I;
5. * Remove from V the nodes in the set W and all their neighbours.
6. Return I.

• If, in step i, we select, where D is the maximum degree of a node in the graph, then WHP all nodes remaining after step i have degree at most. Thus, after log steps, all remaining nodes have degree 0, and can be removed in a single step.
• If, in any step, the degree of each node is at most d, and we select , then WHP the longest path in the directed graph determined by the fixed ordering has length. Hence the fully parallel algorithm takes at most steps.
• Combining these two facts gives that, if we select, then WHP the run-time of the partially parallel algorithm is.

  Listing all maximal independent sets

Parallelization of finding maximum independent sets

History

Complexity class

Communication and data exchange