On the Parameterized Complexity of Computing Balanced Partitions in Graphs

René van Bevern, Andreas Emil Feldmann, Manuel Sorge, Ondřej Suchý

Результат исследования: Научные публикации в периодических изданияхстатья

9 Цитирования (Scopus)

Аннотация

A balanced partition is a clustering of a graph into a given number of equal-sized parts. For instance, the Bisection problem asks to remove at most k edges in order to partition the vertices into two equal-sized parts. We prove that Bisection is FPT for the distance to constant cliquewidth if we are given the deletion set. This implies FPT algorithms for some well-studied parameters such as cluster vertex deletion number and feedback vertex set. However, we show that Bisection does not admit polynomial-size kernels for these parameters. For the VertexBisection problem, vertices need to be removed in order to obtain two equal-sized parts. We show that this problem is FPT for the number of removed vertices k if the solution cuts the graph into a constant number c of connected components. The latter condition is unavoidable, since we also prove that VertexBisection is W[1]-hard w.r.t. (k,c). Our algorithms for finding bisections can easily be adapted to finding partitions into d equal-sized parts, which entails additional running time factors of nO(d). We show that a substantial speed-up is unlikely since the corresponding task is W[1]-hard w.r.t. d, even on forests of maximum degree two. We can, however, show that it is FPT for the vertex cover number.

Язык оригиналаанглийский
ЖурналTheory of Computing Systems
Том57
Номер выпуска1
DOI
СостояниеОпубликовано - 8 июл 2015
Опубликовано для внешнего пользованияДа

Fingerprint Подробные сведения о темах исследования «On the Parameterized Complexity of Computing Balanced Partitions in Graphs». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать