Min-cut on subgraphs of G

Question

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

Given a undirected connected graph G=(V,E)(|V|≤100,|E|≤4000) and some subgraphs of G: G_1,G_2,...,G_n(n≤32), and all G_i is connected and include all the vertexs in G. We need to cut some edges in G so that all of the subgraphs G_1,G_2,...,G_n become NOT connected. 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? :)

The problem is NOT sufficient to make G disconnected.
Example: Consider G = ({1,2,3,4},{(1,2),(1,3),(1,4),(2,4),(3,4)}), G_1 = ({1,2,3,4},{(1,2),(1,3),(1,4)}), G_2 = ({1,2,3,4},{(4,1),(4,2),(4,3)}). The best solution is to cut edge (1,4).

ravenspoint · Answer

Have you tried the brute force search algorithm? Since your maximum problem size is modest ( |V|≤100,|E|≤4000, n < 32 ) an efficient code should find the solution in a few minutes.

LOOP MCE over 1 to E
    LOOP CE over combinations of MCE in E
       CUT edges in CE
       SET OK = TRUE
       LOOP S over subgraphs 
          IF S is connected
              SET OK = FALSE
              BREAK ( S over subgraphs )
       IF OK == TRUE
          OUTPUT MCE and CE
          STOP
       RESTORE edges in CE
    IF time exceeded
       OUTPUT "no solution in time available"
       STOP
OUTPUT "no solution"
STOP

Min-cut on subgraphs of G

1 Answers