How to get the minimum cost of disconnecting some node from each other in a graph

Question

In a given graph, i want to calculate the minimum cost of disconnecting some node from each other in a graph. Example:
In this graph, let say i want to disconnect node A, node C and node F with each other by removing some edges among these nodes. i.e. by removing edge A-B and edge F-E, the nodes A, C and F will be disconnected. Here cost means the length of the edge which is being removed. in this example total minimum cost for disconnecting Node A, Node C and Node F from each other is 2+1=3.
Can somebody provide some hint. I am unable to categorize this problem, whether this is a kind of shortest path problem or minimum spanning tree problem?

Answer 1

This is called the multiterminal cut problem. Unfortunately there seems not to be a Wikipedia entry. The problem is, given a weighted graph and a subset of vertices called the terminals, compute the minimum-weight set of edges whose removal disconnects every pair of terminals. The bad news is that this problem is NP-hard, so if you really need an optimal solution on an instance that can't be brute forced, you'll probably have to turn to integer programming. The good news is that there's a simple 2-approximation algorithm (not the best factor known, but you may have to brush up on your linear programming and read the research literature to use the "better" ones), which can be achieved by taking the union of s-t cuts separating each terminal from the others.