The problem says that given a weighted edge bidirectional graph, find the set of edges, by deleting which a given set of nodes becomes disconnected with each other. And also the sum of these edge weights should be minimum. Does this problem has any name? Any particular algorithm to solve them? I know that this must be the NP complete problem.
1
- 3The problem is called "minimum k-cut" or "minimum multiterminal cut", see Wikipedia for references.n. m. could be an AI– n. m. could be an AI2012-04-26 19:15:00 +00:00Commented Apr 26, 2012 at 19:15
Add a comment |
1 Answer
If you just want to find a minimum weight cut which departs your graph into two part, this simply can be done by running max flow/min cut algorithm (e.g Edmonds algorithm). You just should fix one vertex and then find its min cut with all other |V|-1 vertices, finally out put minimum cut among all cuts. Note that your fixed vertex should be in one of a components. For running max-flow/min cut algorithm on undirected graphs just draw each edge into two direction. This algorithm causes to running max-flow algorithm * O(|V|).
But if your problem is how to divide the graph into k connected component with minimum weight cut, this is NP-Hard problem.
