A note on partition into triangles parametrized by tree-width.
Dušan Knop · arXiv (Cornell University) · 2015
We study the parametrized complexity of the Partition into Triangles problem. For this problem a (simple) graph with 3n vertices is given and the question is whether it is possible to cover its vertices with n triangles (complete graphs on 3 vertices). We prove that there is an FPT algorithm that decides the Partition into Triangles problem and that the existence of a polynomial size kernel is unlikely (unless NP $\subseteq$ coNP/poly).