On the Parameterized Complexity of Computing Balanced Partitions in Graphs

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

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

Abstract

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.

Original languageEnglish
JournalTheory of Computing Systems
Volume57
Issue number1
DOIs
Publication statusPublished - 8 Jul 2015
Externally publishedYes

Keywords

  • Bisection
  • Cliquewidth
  • NP-hard problems
  • Problem kernelization
  • Treewidth reduction

Fingerprint Dive into the research topics of 'On the Parameterized Complexity of Computing Balanced Partitions in Graphs'. Together they form a unique fingerprint.

Cite this