Parameterized Complexity of Graph Partitioning into Connected Clusters
share
Given an undirected graph G and q integers n_1,n_2,n_3, ⋯, n_q, balanced connected q-partition problem (BCP_q) asks whether there exists a partition of the vertex set V of G into q parts V_1,V_2,V_3,⋯, V_q such that for all i∈[1,q], |V_i|=n_i and the graph induced on V_i is connected. A related problem denoted as the balanced connected q-edge partition problem (BCEP_q) is defined as follows. Given an undirected graph G and q integers n_1,n_2,n_3, ⋯, n_q, BCEP_q asks whether there exists a partition of the edge set of G into q parts E_1,E_2,E_3,⋯, E_q such that for all i∈[1,q], |E_i|=n_i and the graph induced on the edge set E_i is connected. Here we study both the problems for q=2 and prove that BCP_q for q≥ 2 is W[1]-hard. We also show that BCP_2 is unlikely to have a polynomial kernel on the class of planar graphs. Coming to the positive results, we show that BCP_2 is fixed parameter tractable (FPT) parameterized by treewidth of the graph, which generalizes to FPT algorithm for planar graphs. We design another FPT algorithm and a polynomial kernel on the class of unit disk graphs parameterized by min(n_1,n_2). Finally, we prove that unlike BCP_2, BCEP_2 is FPT parameterized by min(n_1,n_2).
READ FULL TEXT