7
$\begingroup$

I am reading the paper Color Coding by Alon, Yuster, and Zwick. They state a theorem (6.3) that says if $H$ is a graph on $k$ vertices with treewidth $t$ and $G = (V, E)$, then a subgraph of $G$ isomorphic to $H$ can be found in $2^{O(k)}V^{t+1}$ expected time. They do not include a proof, but do state that the proof is similar to the case where $H$ is a forest (namely theorem 6.1, which they do provide a proof of).

As I am trying to understand how they algorithm would work for graphs of bounded treewidth, I was wondering if anyone could provide a proof sketch of the algorithm, as I don't see how it would be similar to the proof of 6.1 - Any help would really be appreciated, as this is for a course project, and I am having difficulties figuring out the algorithm.

A copy of the paper can be found here: http://www.tau.ac.il/~nogaa/PDFS/col5.pdf

$\endgroup$
3
$\begingroup$

The idea is to repeat the proof of Theorem 6.1, only during the recursive construction in the second paragraph, we use the tree decomposition of $H$ rather than $H$ itself. We pick a vertex in the tree decomposition, which correspond to up to $t+1$ vertices of $H$, and split $H$ into two parts $H',H''$ accordingly, applying the algorithm recursively. Since we are dealing with groups of up to $t+1$ vertices at a time, we have to calculate the color sets for sets of $t+1$ vertices rather than for single vertices.

There are many resources online for this general approach, dynamic programming for graphs of bounded treewidth. You can consult Section 2.4 of Hajiaghayi's thesis or a presentation by Marx.

$\endgroup$
3
  • $\begingroup$ Could you provide a bit more information as to how the colorsets for $t + 1$ vertices are computed? Is that what correspondents to the portion $V^{t+1}$ in the runtime? $\endgroup$
    – user4734
    Mar 19 '14 at 1:55
  • $\begingroup$ I'm afraid you'll have to work this out yourself. The $V^{t+1}$ factor indeed comes from the fact that we have to assign colorsets to ordered sets of $t+1$ vertices. $\endgroup$ Mar 19 '14 at 2:36
  • $\begingroup$ I finally got this. I thought it was easier to think about with a nice tree decomposition instead. $\endgroup$
    – user4734
    Mar 28 '14 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy