Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?
share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.