Next: Lower bound for MIS Up: Locality and Graph Algorithms Previous: The Model

## Maximal Independent Set in the Ring

We now study the maximal independent set (henceforth MIS) problem when the underlying topology is that of a ring (see Figure 10.2). An independent set in a graph is a set of vertices no two of which are adjacent. An independent is maximal if no vertex can be added to the independent set. This is not the same thing as a maximum independent set. An independent set is a useful structure because in some situations it defines a set of mutually compatible operations, i.e. operations that can be executed simultaneously. In spite of its simplicity, the ring topology is interesting because many networks, especially local area networks, are connected in such fashion.

We are going to show matching upper and lower bound for this problem, a very rare event in complexity theory. Our aim is to prove the following theorem.

Theorem 12877

is the complexity of calculating a MIS in the ring.

The function is the iterated logarithm function. It is defined as follows:

where

Note that the function grows extremely slowly. For example,

The proof of Theorem 10.1 is divided in two parts. In the first part, we shall give a beautiful algorithm due to Cole and Vishkin [14]. The algorithm works for any bounded degree graph and so, in particular, for the ring. Let G be the input graph and let denote its maximum degree. The general outline of the algorithm is as follows.

1.
Compute a vertex coloring of G using constantly many colors , where k depends on .
2.
For all colors :in parallel, add each vertices v with color c to the independent set and remove all of its neighbours.

Step 2 clearly computes a MIS in constantly many rounds. The problem then, and the heart of the algorithm, is how to find the coloring of step 1.

The idea of the algorithm is to start with a legal coloring which uses many colors and to shrink it step by step. The initial coloring uses n colors and is given by the ID assignment. We shall consider the binary representation of the colors. A shrinking'' step is as follows. Assume that G is properly colored with m colors. Let cu denote the color of u. Then, each vertex u will build a vector Du as follows: u fixes an arbitrary ordering of the neighbours and for each neighbour v it sets Du(v)=(d(u,v),bu) where d(u,v) is the first bit position starting from the left such that cu and cv differ, and bu is the bit value of cu for that position. The new colour of u is Du.

We claim that (a) the Du's are a valid coloring of the graph, (b) repeating this procedure for steps we will find a coloring using constantly many colors. Since each step requires constantly many communication rounds this is also the complexity of the algorithm.

We first establish (b). How many bits do we need to write down Du? This vector has at most entries, one for each neighbour. Each entry needs bits since d(u,v) is an arbitrary bit position of cv and cv has at most bits. The length of the Du's is then given by the following recurrence:

So, the length shrinks of a log factor for each iterations and it will converge in steps to the (rounded) solution of the equation

which is a constant dependent on .Since the final number of bits is constant, the final number of colors is also constant.

We then establish (a). We want to show that for any two neighbours u and v we have .Let and .What makes the proof difficult is that the order in which u and v write down'' the differences with the neighbours do not need to be consistent. There are two cases:

• There is an index i such that .In this case there is nothing to prove, as the two vectors are certainly different.
• For all i, di = ei. Let's then look at the coordinate which u used to write down its difference from v. Let this coordinate be j. Since di=ei for all i, we know that dj and ej refer to the same bit position. It must then be that since these are the bit values of, respectively, cu and cv at the first position starting from the left at which they differ.

We have thus shown the following result, which implies the first half of Theorem 10.1.

Theorem 12946

The algorithm by Cole and Vishkin computes a MIS of bounded degree graphs in rounds.

Next: Lower bound for MIS Up: Locality and Graph Algorithms Previous: The Model
Viggo Kann
Sat Dec 20 23:41:16 MET 1997