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 $kin 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 $Vsetminus 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?