Bisecting a Four-Connected Graph with Three Resource Sets

Let G=(V,E) be an undirected graph with a node set V and an arc set E. G has k pairwise disjoint subsets T1,T2,...,Tk of nodes, called resource sets, where |Ti| is even for each i. The partition problem with k resource sets asks to find a partition V1 and V2 of the node set V such that the graphs induced by V1 and V2 are both connected and |V1 ∩ Ti|=|V2 ∩ Ti|=|Ti|/2 holds for each i=1,2,...,k. The problem of testing whether such a bisection exists is known to be NP-hard even in the case of k=1. On the other hand, it is known that that if G is (k+1)-connected for k=1,2, then a bisection exists for any given resource sets, and it has been conjectured that for k≥ 3, a (k+1)-connected graph admits a bisection. In this paper, we show that for k=3, the conjecture does not hold, while if G is 4-connected and has K4 as its subgraph, then a bisection exists and it can be found in O(|V|3 log |V|) time. Moreover, we show that for an arc-version of the problem, the (k+1)-edge-connectivity suffices for k=1,2,3.