Thursday, February 14, 2008

Notes on the group Steiner tree proof

A few notes on the rounding proof (and how to complete it):
1. When you round down the $x_e$ values to the power of $2$ below it, note that you might violate the minimality of the solution: e.g., if an edge has value $x_e = 3/4$, and has two children of value $x_{e1} = 1/2$ and $x_{e2} = 1/4$, then rounding down would give $x'_e = 1/2$ but would maintain $x'_{e1} = 1/2$ and $x'_{e2} = 1/4$.

This kind of situation would cause some concern if we want to "merge" edges with identical values in the last step of the preprocessing: how would we merge $e$ and $e1$ in this case? The answer is: we would just "contract" the edge $e1$, and hence any children of $e1$ would now become children of $e$. The key observation is the random process on this new contracted graph connects the same set of leaves to the root as on the original uncontracted graph, since $x'_{e1} = x'_e$.

(Aside: the procedure is fairly robust, so you could alter the procedure and add a step to regain the minimality. Or you could just forget about the last "merging" step entirely. Note that we now no longer have a tree of "height" $\log |g|$, and the closing arguments would now change slightly.)

2. The argument to compute $\Delta$: suppose the height of the "merged" tree is $H$.

For some vertex $u \in g$, let us first show that $\Delta_u = \sum_{w \sim u} Pr[E_u \cap E_w] \le O(H) \times x'_u$. Summing this over all $u \in g$ gives us $O(H)$, since the $x'_u$'s sum up to at most $1$, and hence completes the proof.

For any $w \in g$, let $e$ be the lowest edge shared by the path from $u$ to the root, and the path from $w$ to the root. A moment's thought tells us that $Pr[ E_u ] = x'_u$, and $Pr[ E_w | E_u ] = x'_w/x'_e$ $Pr[ E_w | E_u ] = x'_u/x'_e$. Hence, $Pr[E_u \cap E_w] = (x'_u x'_w / x'_e)$.

Now, if we sum over all $w$ such that the paths from $u$ to root, and $w$ to root have the edge $e$ as their least common ancestor edge as above. Now use the fact that $\sum_{such w} x'_w \leq O(x'_e)$, since all the flow going to such $w$'s must have been supported on the edge $e$ before rounding down. Hence, the sum of $Pr[E_u \cap E_w]$ over all the relevant $w$ for some edge $e$ is $O(x'_u)$.

Finally, the tree is of height $H$, which means there are at most $H$ such terms, giving us $O(H) x'_u$ as claimed.

3. Aravind Srinivasan has some notes on Janson's inequality: it explains how the "simple" structure of the events $E_i$ and (the independence of the random variables determining these events) allow us to prove such a strong inequality. Joel Spencer also has slides on the proof: in fact, he states it in exactly the form we needed today, with his "bad" events $B_i$ being our "good" events $E_v$!

Anonymous said...

Hi folks, looks like an interesting course! I'd just like to comment that the maximum possible value of Delta can be determined without altering the edges' LP values -- see the paper
of Goran Konjevod, R. Ravi and myself. (See Thm. 3.2 and Sec. 3.1.) That paper deals with Covering Steiner, a generalization of Group Steiner where each group i has a requirement k_i. In particular, for Group Steiner, we get that Delta <= ln N.

aravind

Anupam said...

thanks, Aravind!

Another point I forgot to mention in class was that the analysis showing that each group gets connected with probability $1/\log |g|$ is tight. (The original paper of Garg et al points this out as well.)

Here's the example: take a complete binary tree with $g$ leaves, where the $x_e$ values on edges go down by a factor of $2$ at every level. A simple calculation shows that we will hit at least one of the leaves with probability $\approx 1/height$.

Anonymous said...

A minor typo:

$Pr[ E_w | E_u ] = x'_w/x'_e$

and not

$Pr[ E_w | E_u ] = x'_u/x'_e$

Anupam said...

fixed, thanks!