# 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)$, and a set $S = \{S_1, S_2,..., S_n\}$, where each $S_i$ is a subset of $V$. How can I partition $V$ into $k$ subsets such that it is guaranteed that:

1. for each $i$, every node in $S_i$ is in the same subset
2. each subset represents a connected subgraph of $G$?
-
I don’t think that you alwasy can. What if one of the $S_i=G$ and $k>1$? What if $G=K_3$ with nodes $v_1,v_2,v_3$, $S=\{\{v_1,v_2\},\{v_1,v_3\}\}$, and $k=2$? –  Brian M. Scott Jul 26 '11 at 17:02
Is there any constraint on the size of each set? –  Tsuyoshi Ito Jul 26 '11 at 20:52