Some solutions were provided by students. In observance of Swedish customs their identity is not disclosed (Elitism is not politically correct).
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.
for color :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.
in parallel, each vertex with color c picks a new color not used by any neighbour (both A-neighbours and B-neighbours are considered).
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
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
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
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.
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.