Bisecting a 4-connected graph with three resource sets Original Research Article

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