R-BBG_2: Recursive Bipartition of Bi-connected Graphs
share
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.
READ FULL TEXT