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 journal › Article › peer-review
}
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