Problems (from “Parameterized Algorithms” textbook):

Does a graph \(G\) contain \(k\) vertex-disjoint triangles?

Does a graph \(G\) contain a subgraph isomorphic to a \(k\)-vertex tree \(T\)?

In fact, these are both special cases of a more general result: there is (I’m pretty sure) a \(2^{O(k)}n^{O(1)}\) algorithm for detecting whether any \(k\)-vertex pattern graph of treewidth \(100\) (or whatever your favorite constant is, just be warned that the constant is gonna make its way into the big-O, because subgraph isomorphism for clique is probably W1-hard.) occurs as a subgraph of your graph. Maybe I’ll try to think about how to do that in a moment.

Theorem. \(2^{O(k)}n^{O(1)}\) algorithm for triangle packing.

Proof. Color code with \(3k\) colors. Hope that each of the \(3k\) vertices we need for our triangles got a distinct color, this happens with probability at least \(2^{-O(k)}\).

Now we do dynamic programming. For any subset \(C\subseteq [3k]\) of size a multiple of \(3\) define Let \(S[C]\) to be the boolean indicating whether there are \(|C|/3\) vertex disjoint triangles that can be made by using each color from \(C\) exactly once.

Then we can recursively compute \(S[C]\) as follows:

for c1,c2,c3 in C:
  if there is a c1,c2,c3 triangle and S[C - c1c2c3]:
    YES
  else:
    NO

Theorem. \(2^{O(k)}n^{O(1)}\) algorithm for subgraph isomorphism with a tree pattern graph.

Proof. Color code.

Root the pattern tree, and for each vertex decide on a precednece order for its children. There is a certain class of subtrees, indexed by edges, that will be important for us. Namely, the subtree associated with the \(i\)-th edge we call \(S_i\) and it is defined as follows: let edge \(i\) have vertex \(u\) closer to the root and vertex \(v\) farther from the root. So in \(S_i\) we take \(u\), \(T_v\) (the tree rooted at vertex \(v\)), and then also \(w, T_w\) for any children \(w\) of \(u\) which are higher precedence than \(v\).

Now we define the dynamic program. For each vertex \(v\in V(G)\), each edge \(i\) in the pattern graph and each color subset \(C\subseteq [k]\) we will compute \(D[v, i, C]\) which is the boolean “Can we find a copy of \(T_i\) in \(G\) where the root of \(T_i\) is placed at vertex \(v\) and we use precisely the colors \(C\) for the edges of this copy of \(T_i\)?”

Now we show how to compute \(D\) recursively. For edges \(i\) corresponding to edges to low-precedence leaves in the tree its easy to fill in the DP: these guys are fine if \(v\) has a color from \(C\) and \(v\) has a neighbor of the other color.

There are two cases in the induction:

  • sibling
  • child

Child is very easy: just itterate over neighbors of \(v\) and check if any of them can do the subtree we need.

Sibling is as follows: itterate over partitions of the colors that you’re allowed to use. Check for the “\(T_{i-1}\)” i.e., it’s left sibling and also for the subtree thing that you need.

ink_img012