R-BBG\(_2\): Recursive Bipartition of Bi-connected Graphs

Abstract

Given an undirected graph \(G(V, E)\), it is well known that partitioning a graph \(G\) into \(q\) connected subgraphs of equal or specificed sizes is in general NP-hard problem. On the other hand, it has been shown that the q-partition problem is solvable in polynomial time for q-connected graphs. For example, efficient polynomial time algorithms for finding 2-partition (bipartition) or 3-partition of 2-connected or 3-connected have been developed in the literature. In this paper, we are interested in the following problem: given a bi-connected graph \(G\) of size \(n\), can we partition it into two (connected) sub-graphs, \(G[V_1]\) and \(G[V_2]\) of sizes \(n_1\) and \(n_2\) such as both \(G[V_1]\) and \(G[V_2]\) are also bi-connected (and \(n_1+n_2=n\))? We refer to this problem as the recursive bipartition problem of bi-connected graphs, denoted by R-BBG\(_2\). We show that a ploynomial algorithm exists to both decide the recursive bipartion problem R-BBG\(_2\) and find the corresponding bi-connected subgraphs when such a recursive bipartition exists.