1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – jsitesting
    Apr 26 at 14:35
  • $\begingroup$ Correct. And since you try all permutations of colours, then you'll find $k$ triangles if it is a yes instance. $\endgroup$
    – Pål GD
    Apr 26 at 14:36

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.