# Select fixed-size connected induced subgraphs in a graph

I have a connected graph with $$nk$$ vertices, and would like to select $$n$$ disjoint induced subgraphs with $$k$$ vertices such that each subgraph is connected, selecting one out of all possible solutions at random. It doesn't necessarily need to be uniformly at random, I just want the possibility of getting any possible solution.

For example, with this graph: and $$k=3$$, $$n=2$$, here is a solution (in fact it's the only one): And here's one of the two possible solutions for the same graph with $$k = 2$$ and $$n = 3$$: Sometimes this is not possible, like with this graph, for $$k = 3$$ and $$n = 2$$: Is there any (efficient) way of determining whether there is a solution, and if so, selecting one (not necessarily uniformly) at random?

• Checking whether the partition exists is NP-hard: "On the complexity of partitioning graphs into connected subgraphs" has some references and shows that this holds even for planar graphs.
– user114966
Apr 18, 2021 at 18:43
• @Dmitry Thanks! I figured this had already been looked into before, but wasn't sure what to google... Apr 18, 2021 at 18:53