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?
