Partitioning a graph into connected subgraphs with sets of vertices that must be in the same subgraph

I have a connected, undirected graph G = (V, E), a set S = {S_1, S_2,..., S_n} where each S_i is a subset of V, and a k > 1. How can I partition V into k subsets such that it is guaranteed that:

1. for e开发者_运维技巧ach i, every node in S_i is in the same subset
2. each subset represents a connected subgraph of G?

The Steiner forest problem is, given a weighted graph G = (V, E) and pairs of vertices (s₁, t₁), …, (s_m, t_m), find the lightest edge-subgraph H of G such that, for all i, vertices s_i and t_i belong to the same connected component of H.

The decision version of your problem is essentially the decision version of Steiner forest with unit weights. Unfortunately, this special case is still NP-hard.

The reduction from the special case of Steiner forest to your problem is, given an unweighted instance of Steiner forest and instructions to determine whether there exists a solution of cost at most c, create an instance of your problem with the same graph, k = |V| - c, and, for all i, let S_i = {s_i, t_i}. If there exists a Steiner forest of cost at most c, then the connected components of the forest are your subsets, which number at least |V| - c = k. Conversely, if the instance of your problem has a solution, then we can find a spanning tree within each of your subsets, and the total cost is at most |V| - k = c.

The best approximation ratio known is 2, which won't help you much if k is small. You'll probably have to use branch and bound.

Some random observations. You may not be able to join two S_i, S_j because they do not form a connected subgraph. Since the graph is connected, you can always connect them if you just add enough other S_k - eventually you'll end up with the full graph which is connected by definition. So the connectivity requirement drives you towards merging. The requirement of k subsets however drives you towards keeping things apart. Basically, you have a n^k search space which you can radically prune if you keep track of those conditions. Of course if you have "free" nodes in no S, that changes the game completely.

Yeah well not really an answer, rather a beginning of one. Will post anyhow ;)