0
$\begingroup$

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})$.

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

$\endgroup$
7
  • 3
    $\begingroup$ Does this answer your question? Time complexity for FPT algorithm $\endgroup$ – Pål GD Apr 28 at 10:33
  • 2
    $\begingroup$ no, the answer is for the first method while I asked about the second method. and still i don`t understand why is it O∗((2e)3k)? $\endgroup$ – KSGG Apr 28 at 10:47
  • 1
    $\begingroup$ 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. $\endgroup$ – j_random_hacker Apr 28 at 10:50
  • 1
    $\begingroup$ 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. $\endgroup$ – Pål GD Apr 28 at 10:58
  • $\begingroup$ 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) $\endgroup$ – KSGG Apr 28 at 14:54
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.