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?
The problem is unfortunately NP-hard.
Thanks to Dmitry for finding this:
https://www.sciencedirect.com/science/article/pii/0166218X85900083.