# k disjoint triangles with graph splitting to two distinct groups

Please note that this question is different than this question.

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

Now, Let's assume that we get a group $$X \subseteq V$$ of vertices, and the problem changes: Are there $$k$$ vertex-disjoint triangles in $$G$$ where one vertex is from $$X$$ and the other two are from $$V \setminus X$$?

I need to find an algorithm whose running time is $$O^{*}((2e)^{2k})$$. I tried coloring all vertices from $$X$$ in a single color, but I couldn't find a way to avoid the duplicate choices of vertices from $$X$$. I also try to color each vertex from $$X$$ in a distinct color that is different from the colors of $$V\setminus X$$ but the running time is higher.

Can you propose a coloring method that will highlight a possible solution within the required complexity? Should I try something else?

Color the vertices in $$V \setminus X$$ with $$2k$$ colors at random. With probability $$e^{-2k}$$, the $$V \setminus X$$ vertices of your $$k$$ disjoint triangles will be highlighted.
Suppose without loss of generality that $$X = [m]$$. Using dynamic programming, determine for each subset $$S \subseteq [2k]$$ and $$i \in [m]$$ whether there exist $$|S|/2$$ disjoint triangles using the colors in $$S$$ and vertices $$1,\ldots,i$$ of $$X$$. This takes time $$O^*(2^{2k})$$.