0
$\begingroup$

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? :)

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Pål GD
    Sep 10, 2022 at 19:02
  • $\begingroup$ 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 $\endgroup$
    – D.W. ♦
    Sep 10, 2022 at 19:15
  • $\begingroup$ Cross-posted: stackoverflow.com/q/73671543/781723, cs.stackexchange.com/q/154076/755. Please do not post the same question on multiple sites. $\endgroup$
    – D.W. ♦
    Sep 10, 2022 at 19:19
  • $\begingroup$ It's a more general version of a multicut problem, which is NP-hard. I don't see how the additional constraints help. $\endgroup$
    – Dmitry
    Sep 11, 2022 at 1:39

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.