Homework 4

Q1.

PRAM VS. MESSAGE PASSING

1.

Let G be a path with n vertices. Prove an $\Omega(n)$ lower-bound for 2-coloring in the distributed model

2.

A tour in a graph G is a closed walk which traverses each edge at least once. An Euler tour is a tour that traverses each edge exactly once. A graph G is eulerian if it contains an Euler tour. Let G be eulerian. Prove an $\Omega(n)$ lower-bound for computing Euler circuits in the distributed model.

3.

Prove an $\Omega(n)$ lower-bound for computing $\Delta$-edge colorings of bipartite graphs in the distributed model, for any $\Delta$.

4.

OPEN PROBLEM: Improve on the trivial $\Omega(\log^* n)$lower bound for computing $(\Delta+1)$-edge colorings in the distributed model.

Remark: in the PRAM model the first three problems can be solved in polylogarithmic time. This shows that once we charge for local computation, the PRAM is more powerful that the distributed model.

Q2.

COLORING. Let G be a graph with n vertices and maximum degree D. As usual, assume that the vertices know their own ID.

1.

Give a distributed, deterministic algorithm for (D+1)-vertex coloring running in $O(D \log n)$ rounds;

2.

Give a distributed, randomized algorithm for (D+1)-vertex coloring running in expected $O(\log n)$ rounds;

3.

OPEN PROBLEM: Give a distributed, deterministic algorithm for (D+1)-vertex coloring running in polylogarithmically many, in n, rounds.

Q3.

TOUGH NUTS.

1.

Prove the following.

Lemma 13762

Let n > D be two positive integers and let $m = 5 \lceil D^2 \log n \rceil$.There exists a family of sets $F=\{S_i: S_i \subseteq [m], \; 1 \le i \le n \}$ such that, for any collection $S_{i_0}, \ldots, S_{i_D}$, then

$$S_{i_0} \not \subseteq \cup_{k=1}^D S_{i_k}.$$

(Hint: use the probabilistic method).

2.

Using the above lemma, give a deterministic, distributed algorithm for vertex coloring a graph G which uses $O(\Delta^2 \log \Delta)$ colors and runs in $O(\log^*n)$ rounds. (Hint: recall the swift $O(\log^*n)$ algorithm for computing MIS' in the ring).

3.

Show that the existence of an $O(\log^*n)$ algorithm for MIS in the ring implies that there exists a constant c such that $R(2,k,k+2) \ge T(k/c)$.How good is your value of c?