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.

  

Figure 10.2: Ring graph

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

 $\Theta(\log^*n)$ is the complexity of calculating a MIS in the ring.

The $\log^*n$ function is the iterated logarithm function. It is defined as follows:

$$\log^*n=\min\{i\geq0:\log^{(i)}n\leq1\}$$

where

Note that the $\log^*n$ function grows extremely slowly. For example, $\log^*(2^{65536})=5.$

The proof of Theorem 10.1 is divided in two parts. In the first part, we shall give a beautiful $O(\log^*n)$ 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 $\Delta$ denote its maximum degree. The general outline of the algorithm is as follows.

1.

Compute a vertex coloring of G using constantly many colors $c_1,c_2,\cdots,c_k$, where k depends on $\Delta$.

2.

For all colors $c:=1 \ldots k$: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 c_u denote the color of u. Then, each vertex u will build a vector D_u as follows: u fixes an arbitrary ordering of the neighbours and for each neighbour v it sets D_u(v)=(d(u,v),b_u) where d(u,v) is the first bit position starting from the left such that c_u and c_v differ, and b_u is the bit value of c_u for that position. The new colour of u is D_u.

We claim that (a) the D_u's are a valid coloring of the graph, (b) repeating this procedure for $O(\log^*n)$ 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 D_u? This vector has at most $\Delta$ entries, one for each neighbour. Each entry needs $1+\log \log m$ bits since d₍u,v) is an arbitrary bit position of c_v and c_v has at most $\log m$ bits. The length of the D_u's is then given by the following recurrence:

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

$$x = \Delta ( \log x +1 )$$

which is a constant dependent on $\Delta$.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 $D_u \neq D_v$.Let $D_u = [(d_1,b_1), (d_2,b_3), \ldots, (d_{\Delta},b_{\Delta})]$and $D_v = [(e_1,c_1), (e_2,c_3), \ldots, (e_{\Delta},c_{\Delta})]$.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 $d_i \neq e_i$.In this case there is nothing to prove, as the two vectors are certainly different.
• For all i, d_i = e_i. Let's then look at the coordinate which u used to write down its difference from v. Let this coordinate be j. Since d_i=e_i for all i, we know that d_j and e_j refer to the same bit position. It must then be that $b_j \neq c_j$since these are the bit values of, respectively, c_u and c_v 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 $O(\log^*n)$ rounds.