Standard

On the Parameterized Complexity of Computing Balanced Partitions in Graphs. / van Bevern, René; Feldmann, Andreas Emil; Sorge, Manuel et al.

In: Theory of Computing Systems, Vol. 57, No. 1, 08.07.2015.

Research output: Contribution to journalArticlepeer-review

Harvard

van Bevern, R, Feldmann, AE, Sorge, M & Suchý, O 2015, 'On the Parameterized Complexity of Computing Balanced Partitions in Graphs', Theory of Computing Systems, vol. 57, no. 1. https://doi.org/10.1007/s00224-014-9557-5

APA

van Bevern, R., Feldmann, A. E., Sorge, M., & Suchý, O. (2015). On the Parameterized Complexity of Computing Balanced Partitions in Graphs. Theory of Computing Systems, 57(1). https://doi.org/10.1007/s00224-014-9557-5

Vancouver

van Bevern R, Feldmann AE, Sorge M, Suchý O. On the Parameterized Complexity of Computing Balanced Partitions in Graphs. Theory of Computing Systems. 2015 Jul 8;57(1). doi: 10.1007/s00224-014-9557-5

Author

van Bevern, René ; Feldmann, Andreas Emil ; Sorge, Manuel et al. / On the Parameterized Complexity of Computing Balanced Partitions in Graphs. In: Theory of Computing Systems. 2015 ; Vol. 57, No. 1.

BibTeX

@article{8c95cd749191446a8aa7fd1e69dd0664,
title = "On the Parameterized Complexity of Computing Balanced Partitions in Graphs",
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.",
keywords = "Bisection, Cliquewidth, NP-hard problems, Problem kernelization, Treewidth reduction",
author = "{van Bevern}, Ren{\'e} and Feldmann, {Andreas Emil} and Manuel Sorge and Ond{\v r}ej Such{\'y}",
year = "2015",
month = jul,
day = "8",
doi = "10.1007/s00224-014-9557-5",
language = "English",
volume = "57",
journal = "Theory of Computing Systems",
issn = "1432-4350",
publisher = "Springer New York",
number = "1",

}

RIS

TY - JOUR

T1 - On the Parameterized Complexity of Computing Balanced Partitions in Graphs

AU - van Bevern, René

AU - Feldmann, Andreas Emil

AU - Sorge, Manuel

AU - Suchý, Ondřej

PY - 2015/7/8

Y1 - 2015/7/8

N2 - 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.

AB - 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.

KW - Bisection

KW - Cliquewidth

KW - NP-hard problems

KW - Problem kernelization

KW - Treewidth reduction

UR - http://www.scopus.com/inward/record.url?scp=84937191674&partnerID=8YFLogxK

U2 - 10.1007/s00224-014-9557-5

DO - 10.1007/s00224-014-9557-5

M3 - Article

AN - SCOPUS:84937191674

VL - 57

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 1

ER -

ID: 22340283