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$!
If anything else was unclear, please post questions, comments, or clarifications!


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.


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!