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 $P: u_1 u_2 \cdots u_n$. Consider the two points u_n/4 and u_3n/4 and let $\chi(u_{n/4})$ and $\chi(u_{3n/4})$be the output of the algorithm. Consider now a new network P' which is built from P by inserting u_n between u_n/2 and u_1+n/2. The algorithm should work correctly for P' too but it doesn't. That's because the t-neighborhoods of u_n/4 and u_3n/4 are the same, hence the protocol will compute the same answer, (i.e $\chi'(u_{n/4})=\chi(u_{n/4})$ and $\chi'(u_{3n/4})=\chi(u_{3n/4})$), but the parity between u_n/4 and u_3n/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.

  

Figure 23.1: In any Euler tour e and g must be consecutive, and so must f and h.

For the third question, first we notice that the exercise asked for a lower bound holding for all $\Delta$'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 $\Delta=6$ is shown in Figure 23.2. The gadget has the property that in any $\Delta$-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.

  

Figure 23.2: A and B must receive the same color in any $\Delta$-coloring of the gadget. Here $\Delta=6$.

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 $c:=1 \cdots D+1$:
in parallel, each vertex $u \in B$ with color c picks a new color $c' \in [D+1]$ not used by any neighbour $v \in N(u)$ (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,  

$$\Pr(\mbox{$u$\space colors}) \ge \frac{1}{4}$$ (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 $\Pr(\mbox{$u$\space colors})$ 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 $\{1,2\}, \{2,3\}, \{3,4\}, \ldots, \{d,d+1\}$.Notice that in this case Equation (23.1) holds (almost with equality).

Let A(v) denote v's palette and let a_v=|A(v)|. We can assume without loss of generality that $A(v) \subseteq C$, for all neighbours v, because colors in C-A(v) decrease the probability of tentative color conflict and hence increase $\Pr(\mbox{$u$\space colors})$.

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 $A(v) \subseteq C$ 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 $c \in C$ 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 X_c be the indicator random variable for the event ``c is free'' and let $X=\sum_c X_c$. Then, $E[X_c] = \Pr(X_c=1)$and

Minimizing $\Pr(\mbox{$u$\space colors})$ 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 $v \in N$ and remove the edges incident on it, i.e. all edges (u,c) with $c \in A(v)$.This defines another graph G'[N,C]. For notational convenience, let Y_c be the indicator random variable for the event ``c is free in G''' and let $p_c:=\Pr(Y_c=1)$ and $Y=\sum_c Y_c$. Then,

$$\Pr(X_c=1) = \left\{ \begin{array} {ll} p_c & \mbox{if $c \... ...)$} \ p_c (1-1/a_v) & \mbox{if $c \in A(v)$}\end{array}\right.$$

From this it follows that

$$E[X] = E[Y] - \sum_{c \in A(v)} \frac{p_c}{a_v} .$$

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

$$\sum_{c \in A(v)} \frac{p_c}{a_v}$$

where p_c is the probability of the event ``c is free'' prior to the insertion of the edges $(v,\alpha)$ for $\alpha \in A(v)$.The initial assignment is p_c= 1 for all $c \in C$, corresponding to the empty graph.

Given a set of values $\{p_c: \; c \in C \}$ what is then the best way to pick A(v)? More precisely, what we want is

$$\max_{A(v) \subseteq C} \sum_{c \in A(v)} \frac{p_c}{a_v}.$$

Certainly it does not hurt if we pick the highest a_v values among the p_c's. But how large should a_v be? Assuming wlog that $p_i \ge p_{i+1}$ and recalling that a_v must be at least 2, then 2 is the best possible since

$$\sum_{i=1}^k \frac{p_i}{k} \le \sum_{i=1}^{k+1} \frac{p_i}{k+1}.$$

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

We now have to determine the value of |C| which minimizes $\Pr(\mbox{$u$\space colors})$ subject to $\vert C\vert \ge d+1$. Since the final palettes have size two and it pays off to overlap them as much as possible- for this decreases E[X_c] 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,

$$Pr(\mbox{$u$ colors}) \ge \frac{1}{4}$$

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 $\Pr(\mbox{$u$\space colors} \; \vert \; aw(u))$ 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

$$\Pr( X \gt a) \le \frac{E[X]}{a} \le \frac{\vert A(u)\vert}{2a}.$$

By setting, say, a=3|A(u)|/4 this probability is less then 2/3. Then the event ``$X \le a$'' 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

$$\Pr(\mbox{$u$ colors}) \ge \Pr(\mbox{$u$ colors} \; \vert \;... ...) \Pr(X \le a) \ge \frac{1}{4} \cdot \frac{1}{3} = \frac{1}{12}$$

Q3.

The first two are from [24].

• Let $m = 5 \lceil D^2 \log n \rceil$ and consider a random collection F of n subsets of $\{1,\ldots,m\}$ which is constructed as follows. For $1 \le x \le m$ and $1 \le i \le n$, let $\Pr(x \in S_i)=1/D$.All decisions whether $x \in S_i$ 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 $S_0,S_1,\ldots,S_D$there holds

  $$x \in S_0 - \left ( \cup_{i=1}^D S_i \right )$$

  is

  $$\frac{1}{D} \left ( 1 - \frac{1}{D} \right )^D \ge \frac{1}{4D}.$$

  Therefore, the probability that $S_0 \subseteq \cup_{i=1}^D S_i$is at most ( 1 - 1/4D)^m. The number of ways of choosing $S_0,S_1,\ldots,S_D$ is $(D+1) \left(\frac{n}{D+1}\right)$. Therefore if

  $$\left( 1 - \frac{1}{4D} \right)^m (D+1) \left(\frac{n}{D+1}\right) < 1,$$

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

  $$m \gt 5 D^2 \log n.$$

• Define

  Notice that for $k=O(\log^* n), m_k = O( D^2 \log D)$.For each $1 \le i \le k$, let ${\cal F}_i$ be a family satisfying the above Lemma, i.e. each ${\cal F}_i$ contains m_i elements, where each element is a subset of $\{1,\ldots,m_{i+1}\}$.Given a graph with n vertices we give to each vertex all families ${\cal F}_i$, $1 \le i \le k$.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 S_u from ${\cal F}_1$ and, checking with the neighbours, selects an element x such that (here u denotes both a vertex and its ID)

  $$x \in S_u - \cup_{v \in N(u)} S_v.$$

  Then x becomes the new color of vertex u. Notice that now we have a coloring of the graph using $m_1 = 5 \lceil D^2 \log n \rceil$ colors. In round 2, the family ${\cal F}_2$ is used. Let x(u) denote the new color of vertex u. Each vertex u now picks the set S_x(u) from ${\cal F}_2$ and, checking with the neighbours, selects an element

  $$y(u) \in S_{x(u)} - \cup_{v \in N(u)} S_{x(v)}.$$

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

  $$R(2,k,k+2) \le f(k) =: n$$

  then $t = (k-1)/2 \ge f^{-1}(n)/3$ 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 $t=O(\log^* n)$ steps, therefore $f^{-1}(n)=O(\log^* n)$ which implies f(k)=T(n/c), for some c.