2
$\begingroup$

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:

a cycle of 4 vertices, sharing 1 vertex with a cycle of 3 vertices

and $k=3$, $n=2$, here is a solution (in fact it's the only one):

the vertices in the 3-cycle are grouped together, and so are the remaining 3 vertices

And here's one of the two possible solutions for the same graph with $k = 2$ and $n = 3$:

two pairs of vertices in the 4-cycle are grouped together, as are the remaining 2 vertices

Sometimes this is not possible, like with this graph, for $k = 3$ and $n = 2$:

a path of 4 vertices, with a path of 2 vertices coming out of the second vertex

Is there any (efficient) way of determining whether there is a solution, and if so, selecting one (not necessarily uniformly) at random?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – user114966
    Apr 18 '21 at 18:43
  • $\begingroup$ @Dmitry Thanks! I figured this had already been looked into before, but wasn't sure what to google... $\endgroup$
    – pommicket
    Apr 18 '21 at 18:53
1
$\begingroup$

The problem is unfortunately NP-hard. Thanks to Dmitry for finding this: https://www.sciencedirect.com/science/article/pii/0166218X85900083.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.