Next: Solutions to homework 5 Up: Lecture Notes in Theoretical Previous: Solutions to homework 3

# Solutions to homework 4

Notice:
Some solutions were provided by students. In observance of Swedish customs their identity is not disclosed (Elitism is not politically correct).

Q1.
The basic intuition is that if a protocol runs for t rounds then only processors at distance t or less can communicate. If the t-neighborhood of a vertex is the same in two networks, the vertex will output the same value in both cases. For the first problem, suppose by contradiction that a protocol exists such that (a) it runs in t(n)=o(n) rounds and (b) it computes a 2-coloring of a path of length n. Take n large enough so that t(n)<n/4 and suppose wlog that 4|n. Let the network be the path . Consider the two points un/4 and u3n/4 and let and be the output of the algorithm. Consider now a new network P' which is built from P by inserting un between un/2 and u1+n/2. The algorithm should work correctly for P' too but it doesn't. That's because the t-neighborhoods of un/4 and u3n/4 are the same, hence the protocol will compute the same answer, (i.e and ), but the parity between un/4 and u3n/4 has now changed.

For the second problem the argument is the same. Consider the network N in Figure 23.1. In any Euler tour edges e and g must be consecutive and so must f and h. Suppose now that a new network N' is created by disconnecting A from D and B from C and by connecting A with C and B with D. For large enough n, t(n)=o(n)<n/4, and the t-neighborhood of the 5 points in the middle remains unaffected and hence the output of the algorithm will be the same. In particular, the specifications concerning e,f,g and h do not change But this now does not give an Euler tour.

For the third question, first we notice that the exercise asked for a lower bound holding for all 's. Again, we use the same basic argument. We only need to find an appropriate network. This is done by stringing together copies of a certain gadget. A gadget for is shown in Figure 23.2. The gadget has the property that in any -coloring of it the edges denoted by A and B must receive the same color. The two networks that make the protocol fail are defined as follows. A network N is formed by stringing several gadgets together, where the A-edge of one gadget coincides with the B-edge of the next. Another network N' is formed by removing the rightmost vertex and by inserting it into the middle, thereby splitting the central B-edge into two. Now the same argument can be repeated.

Q2.
1.
Consider the following recursive algorithm. The vertices split into two round i, the vertices look at the i-th digit starting form the left, say, of their ID and split into two sets: the set A of vertices whose i-th bit is 0 and the set B of vertices whose i-th bit is 1. The algorithm recursively computes, in parallel, a (D+1)-coloring of G[A] and G[B]- the graphs induced by the vertices of A and B. This defines a color assignment for the whole graph which however does not take care of edges with one endpoint in A and the other in B. To fix this, we keep the coloring of vertices in A fixed and use the coloring for B as a schedule to recolor B-vertices. This is done as follows:
for color :
in parallel, each vertex with color c picks a new color not used by any neighbour (both A-neighbours and B-neighbours are considered).
This works because (a) the degree of each vertex being at most D, there is always a free c', and (b) B-vertices having the same color c form an independent set and hence their recoloring operations are mutually compatible. The base case of the above algorithm (and of the inductive proof of correctness) is given by isolated vertices or by edges having an two endpoints whose ID differ by just the leftmost bit.
2.
We shall give two algorithms. The first can be considered the simplest possible and is as follows. Each vertex is given a palette of d(u)+1 colors, where d(u) is the degree of u. The algorithm proceeds in rounds. During a round, each uncolored vertex (a) picks a tentative color uniformly and independently from its palette; (b) checks if any neighbour attempting coloring at this round wants the same color; and (c) if the color is not wanted by anybody else it becomes final; otherwise, the attempt fails and the palette is updated (by deleting all colors successfully used by neighbours). We want to show that,
 (17)
for all rounds and each uncolored vertices u.

What makes the analysis interesting is that at any given round, the palettes might be arbitrary subsets of the original sets. We want to show that no matter how u's palette and those of its neighbours look like the bound of Equation (23.1) holds. We will show that the minimum value of is attained when (a) u has a palette of size d+1, where d is the number of u's neighbours, and (b) the neighbours' palettes are .Notice that in this case Equation (23.1) holds (almost with equality).

Let A(v) denote v's palette and let av=|A(v)|. We can assume without loss of generality that , for all neighbours v, because colors in C-A(v) decrease the probability of tentative color conflict and hence increase .

We can then formalize the problem as follows. Consider a bipartite graph G[N,C] where N is the set of neighbours of u and C is the palette of u. A set of palettes for the neighbours of u uniquely corresponds to a graph G[N,C] and vice versa, for each set defines a palette for v and vice versa. Notice that since the palettes never run out of colors, their size is at least two, always. Alternatively, we are considering graphs where the degree of each vertex in N is at least two.

Given a graph G[N,C] consider the following random experiment. Each vertex in N picks one incident edge uniformly and independently at random. A vertex is hit if one of its incident edges is selected and it is free otherwise. This corresponds to a tentative color choice of the neighbours of u in the vertex coloring algorithm. For each c let Xc be the indicator random variable for the event c is free'' and let . Then, and

Minimizing is then equivalent to finding a graph G[N,C] which minimizes E[X].

To solve this problem we argue as follows. Given G[N,C] take any arbitrary vertex and remove the edges incident on it, i.e. all edges (u,c) with .This defines another graph G'[N,C]. For notational convenience, let Yc be the indicator random variable for the event c is free in G''' and let and . Then,

From this it follows that

The problem of selecting the A(v)'s that minimize E[X] is then equivalent to the problem of selecting a sequence of palettes A(v) each time maximizing the value

where pc is the probability of the event c is free'' prior to the insertion of the edges for .The initial assignment is pc= 1 for all , corresponding to the empty graph.

Given a set of values what is then the best way to pick A(v)? More precisely, what we want is

Certainly it does not hurt if we pick the highest av values among the pc's. But how large should av be? Assuming wlog that and recalling that av must be at least 2, then 2 is the best possible since

Notice that this procedure also specifies how to pick the palettes: choose the 2 highest values among the pc's.

We now have to determine the value of |C| which minimizes subject to . Since the final palettes have size two and it pays off to overlap them as much as possible- for this decreases E[Xc] and hence E[X]- the maximum is achieved when |C| is as small as possible. Hence |C|=d+1 (this could be shown more rigorously by another exchange argument similar in spirit to the one above).

Another algorithm, almost identical to the previous one, is as follows. Each vertex is given a palette of d(u)+1 colors, where d(u) is the degree of u. The algorithm proceeds in rounds. At the beginning of each round, each uncolored vertex is asleep. With probability 1/2 each sleeping vertex awakes. An awake vertex then (a) picks a tentative color from its palette; (b) checks if any neighbour attempting coloring at this round wants the same color; (c) if the color is not wanted by anybody else it becomes final; otherwise, the attempt fails, the palette is updated (by deleting all colors successfully used by neighbours) and the vertex goes back to sleep.

All coin flips are independent.

The algorithm is based on the following, rather compelling, intuition. A vertex u is awake with probability half and we expect half of its neighbours to be awake. This means that at least half of the colors in u's palette will not be picked by neighbours so that u has probability half of picking a free color. The total probability of success will then be 1/4. We now formalize this intuition. As before, we want to show that, at each round,

for all uncolored vertices u. Let aw(u) denote the event that u is awake at the current round. Focus on a vertex u. Then,

To estimate we show that the complementary event occurs with probability less than 1/2. By independence of the coin flips,

Recalling that |A(u)| > |N(u)| for all u,

Notice that this analysis only needs pairwise independence.

Alternatively, we could use Markov's inequality in the following way. The expected number of neighbours which are awake is at most |A(u)|/2, as each neighbour awakes with probability 1/2 and there are at most |A(u)| of them. Let X denote the number of neighbours of u which are awake. Then, Markov's inquality states that

By setting, say, a=3|A(u)|/4 this probability is less then 2/3. Then the event '' occurs with probability at least 1/3. Conditioning on this, we have that at most 3|A(u)|/4 neighbours will attempt coloring which means at least 1/4 of the colors will be free for u. Hence

Q3.
The first two are from [24].
• Let and consider a random collection F of n subsets of which is constructed as follows. For and , let .All decisions whether are made independently.

We claim that there is a selection of such a family for which the lemma holds. The probability that for a given x and given there holds

is

Therefore, the probability that is at most ( 1 - 1/4D)m. The number of ways of choosing is . Therefore if

then there is a selection of a family F which satisfies the lemma. Standard estimates show that this holds when

• Define

Notice that for .For each , let be a family satisfying the above Lemma, i.e. each contains mi elements, where each element is a subset of .Given a graph with n vertices we give to each vertex all families , .The computation then proceeds in rounds starting with the initial coloring given by the ID's of the vertices. In round one, each vertex u selects the set Su from and, checking with the neighbours, selects an element x such that (here u denotes both a vertex and its ID)

Then x becomes the new color of vertex u. Notice that now we have a coloring of the graph using colors. In round 2, the family is used. Let x(u) denote the new color of vertex u. Each vertex u now picks the set Sx(u) from and, checking with the neighbours, selects an element

And so on.
• The proof seen in class shows that, for any invertible function f, if

then is a lower bound for computing an MIS in the ring (recall that k=2t-1/2, where t denoted the number of protocol steps to compute the MIS). But we know a protocol which takes steps, therefore which implies f(k)=T(n/c), for some c.

Next: Solutions to homework 5 Up: Lecture Notes in Theoretical Previous: Solutions to homework 3
Viggo Kann
Sat Dec 20 23:41:16 MET 1997