# Time complexity for FPT algorithm

I'm studying the issue of FPT algorithms and came to the k-disjoint triangles problem as can be seen here on slide 60.

The problem summary is given a graph G and variable k, are there k disjoint triangles in the graph. There are two methods, I want to focus on one of them. (Method 1)

First I randomly color the graph in 3k colors and then go over each permutation of colors and check whether there are k triangles with distinct colors.

What I fail to understand is what the time complexity of such examination (going over all the possible permutations) and how exactly can it be done?

Suppose that you have a graph and each vertex is colored with one of three colors, and let the set of different-colored vertices be $$A, B, C$$.

Now, try to find a triangle with one vertex from each partition. For each vertex $$a \in A$$, try let $$B_a$$ and $$C_a$$ be $$a$$'s neighborhood in $$B$$ and $$C$$, respectively. Now you only need to check if there is an edge from $$B_a$$ to $$C_a$$. If there is one, you have your triangle, otherwise, you try another vertex from $$A$$.

Let us call this subroutine colorful_triangle(G, A, B, C). Observe that it is not necessary that $$A \cup B \cup C = V(G)$$.

Let $$G$$ be the graph, $$\chi$$ the coloring and $$\pi$$ a permutation of colors.

Let $$\chi(i)$$ be the set of vertices that received color $$i$$.

Now let $$A = \chi(\pi(1))$$, $$B = \chi(\pi(2))$$, $$C = \chi(\pi(3))$$. Run the subrouting colorful_triangle(G, A, B, C). If successful, continue with $$A = \chi(\pi(4))$$, $$B = \chi(\pi(5))$$, $$C = \chi(\pi(6))$$, and so on.

If you at some point are unsuccessful, move on to the next permutation.

• So if I understand correctly, I need to check for each three colors, whether I have a triangle with those colors, if I find one, I can move on to the next three colors. Otherwise, I should try a different permutation. What could be the worst case in timewise regards? Apr 26 at 14:35
• Correct. And since you try all permutations of colours, then you'll find $k$ triangles if it is a yes instance. Apr 26 at 14:36