# Color coding to get an FPT algoirthm for k disjoint triangles

The k-disjoint triangles problem is as follows:

Input: A graph $$G=(V,E)$$ and an integer $$k\in \mathbb{N}$$

Output: Are there $$k$$ vertex-disjoint triangles in $$G$$?

An FPT algorithm is presented here (starting from slide 60). The algorithm uses color-coding and relies on dynamic programming to determine if a solution is highlighted (each vertex in the solution group is colored with a distinct color). The running time of the algorithm is $$O^∗((2e)^{3k})$$.

Im trying to understand the running time of this algorithm using dynamic programming (method 2). why is it $$O^∗((2e)^{3k})$$?

• Does this answer your question? Time complexity for FPT algorithm Apr 28 at 10:33
• no, the answer is for the first method while I asked about the second method. and still i dont understand why is it O∗((2e)3k)?
– KSGG
Apr 28 at 10:47
• This came up recently, and IIRC the $(2e)^{3k}$ comes from $e^{3k}2^{3k}$, where the first factor is the number of random colourings you need to try to get a constant probability of success (in the case of a YES instance), and the second factor is the time needed to solve the DP for each colouring. Apr 28 at 10:50
• As @j_random_hacker says, it comes from random colorings. An easier example is the example for $k$-PATH on page 54 in the same deck. Now, instead of a $k$-PATH you are looking for $k$ triangles. Apr 28 at 10:58
• I guess I didnt make myself clear enough. but my main problem is that Im not able to see why the DP can be done in 2^3k. how is it possible? as I see it everytime I check a new cell value, I need to check many of his subgroups and I can`t see how it gets done in O(2^3k)
– KSGG
Apr 28 at 14:54

The dynamic programming algorithm goes over all subsets of $$[3k]$$ whose size is a multiple of 3, in nondecreasing order of size. For each such non-empty subset, it goes over all $$O(n^3)$$ triplets of vertices, and for each one, it performs a single table look-up. Therefore the running time is $$O^*(2^{3k} n^3)$$, where $$O^*$$ hides $$\operatorname{poly}(k)$$ factors which are needed to manipulate indices.