Describe a Monte Carlo algorithm for the Triangle Packing problem

Question

Book: Parameterized Algorithms by Marek Cygan (free to download legally)

Chapter about Multivariate polynomials on Page 353 (In the book not the pdf) Question 10.19:

Describe a Monte Carlo $2^{3k}n^{O(1)}$ - time polynomial-space algorithm for the Triangle Packing problem: given a graph $ G $ and a number $ k \in N $, decide whether $ G $ contains $ k $ disjoint triangles (subgraphs isomorphic to K3).

Hint 10.19 in Page 354: Use a similar approach as in the $2^{k}n^{O(1)}$ -time algorithm for $k$-path from this chapter (Page 333).

I tried to solve the problem using the hint, but without success unfortunately, there are solutions to the book? I would be happy to get help if it can be solved even without official solutions of the book but it is important to solve it using the hint they brought in order to use the tools learned in the same chapter.

Thanks in advance.

Answer 1

Although I agree with Yuval, I'll try to get you started on the connection to their longest path approach. The goal is, given a graph $G$, to define a polynomial $P_G$ which is nonzero iff $G$ has $k$ disjoint triangles. If you could evaluate $P_G$ on an arbitrary point in the underlying field $\mathbb{F}$ in time $2^{3k}n^{O(1)}$ then Schwartz-Zippel gives you the desired result (assuming that the degree of $P_G$ is low enough compared to $|\mathbb{F}|)$.

Denote by $T$ the set of all length $3k$ vertex sequences $(v_1,...,v_{3k})$ such that for all $i$ satisfying $i=1\pmod 3$, the triplet $(v_i,v_{i+1},v_{i+2})$ is a triangle in $G$. Now, it is not hard to see that if $\mathbb{F}$ has characteristic 2 then the following polynomial (over $|E|+3k|V|$ variables) is nonzero (i.e. has a nonzero coefficient) iff $G$ contains $k$ disjoint triangles:

$P_G(\pmb{x_e},\pmb{y_{(v,j)}})=\sum\limits_{(v_1,...,v_{3k})\in T}\sum\limits_{l\in S_{[3k]}}\prod\limits_{i\in[3k]}x_{(v_i,v_{i+1})}\prod\limits_{i\in[3k]} y_{i,l(i)}$

Where $S_n$ is the symmetric group. The hard part is evaluating $P_G$ without going over all possible sequences in $T$. The fact that we don't care about repetitions in sequences in $T$ will allow (after some considerable work in rewriting $P_G$) efficient dynamic programming to come into play. The rest pretty much follows the proof for the longest path case (after extending the sum to functions whose range is a subset of $[3k]$, the dynamic programming part would look a bit different, e.g. you would probably want to shorten the sequence by three elements at a time).

Answer 2

Koutis gives an $O^*(2^{3k})$ algorithm for the more general problem of $3$-set $k$-packing in his paper Faster algebraic algorithms for path and packing problems. This was improved by Björklund, Husfeldt, Kaski, and Koivisto in their work Narrow sieves for parameterized paths and packings to $O^*(1.493^{3k})$. I don't know what is the state of the art on this problem.