1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\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.