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 at 18:43
• @Dmitry Thanks! I figured this had already been looked into before, but wasn't sure what to google... Apr 18 at 18:53