# A problem about min-cut on subgraphs

When I was trying to solve a problem, I met another problem like this:

Given a undirected connected graph $$G=(V,E)(|V|\le100)$$ and some subgraphs of $$G$$: $$G_1,G_2,\cdots,G_n(n\le 32)$$, and all $$G_i$$ is connected and include all the vertexs in $$G$$. We need to cut some edges in $$G$$ so that neither of the subgraphs $$G_1,G_2,\cdots,G_n$$ is a connected graph. What's the minimum number of edges we need to cut?

I have tried many ways but all failed. Could anyone please give me an algorithm to solve it? :)

• Have you considered the possibility that the general problem is NP-complete? There might not be a better approach than brute-force. Find a minimal cut in any subgraph and remove it and recurse with budget reduced by the size of a cut. Sep 10, 2022 at 19:02
• What is the context where you encountered this task? What is the motivation? We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing
– D.W.
Sep 10, 2022 at 19:15
• – D.W.
Sep 10, 2022 at 19:19
• It's a more general version of a multicut problem, which is NP-hard. I don't see how the additional constraints help. Sep 11, 2022 at 1:39