I am reading the paper Color Coding by Alon, Yuster, and Zwick. They state a the

Question

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.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.