Charles Explorer logo
🇨🇿

Partitioning Graphs into Induced Subgraphs

Publikace na Matematicko-fyzikální fakulta |
2017

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".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.