Abstrakt
We study the Partition into H problem from the parametrized complexity point of view. In the Partition into H problem the task is to partition the vertices of a graph G into sets V1,...,Vr such that the graph H is isomorphic to the subgraph of G induced by each set Vi for i=1,...,r.
The pattern graph H is fixed. For the parametrization we consider three distinct structural parameters of the graph G - namely the tree-width, the neighborhood diversity, and the modular-width.
For the parametrization by the neighborhood diversity we obtain an FPT algorithm for every graph H. For the parametrization by the tree-width we obtain an FPT algorithm for every connected graph H.
Thus resolving an open question of Gajarský et al. from IPEC 2013. Finally, for the parametrization by the modular-width we derive an FPT algorithm for every prime graph H.