Bisecting a 4-connected graph with three resource sets

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