Is there an algorithm for finding the number of ways a given connected graph can be divided into $k$ connected subgraphs? I've searched the Web for an answer, but perhaps I'm using the wrong words as my graph theory is rusty. Basically, given a set of vertices, I'm looking for the number of ways this set can be split into $k$ disjoint subsets, where each subset of vertices is connected. enter image description here

With the graph example above and $k=3$, a possible division would be {A, B, D}, {C, F, H} and {E, G}. An example of a disallowed subset would be {A, F} as they are not directly connected.


Suppose I narrowed the scope to a grid graph like the one below:

enter image description here

Would that help find an algorithm?

  • $\begingroup$ Are you interested in an actually feasible algorithm to run it on a computer or for theoretic purpose? $\endgroup$ – M. Winter May 22 '17 at 8:50
  • $\begingroup$ @M. Winter: I'm looking for an algorithm to run on a computer, but if you have a more theoretic answer, that would also be welcome. $\endgroup$ – Jens May 22 '17 at 15:35
  • $\begingroup$ Without any restrictions I would just suggest the exhaustive search. That of course is no option for a real program. $\endgroup$ – M. Winter May 23 '17 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.