I'm guessing that this is a standard enough problem, but can't seem to find an intuitive solution.
I have an undirected weighted graph $G = (V,E,f)$ with vertices $V$, edges $E$ and $f$ the weighting function for an edge.
I have a set $\mathbf{I} = \{ I_1, …, I_n \}$ such that for $I \in \mathbf{I}$, $I \subset V$.
I want to perform a minimum-cut type operation on $G$ to produce $G'$ such that no pair of vertices in a set $I \in \mathbf{I}$ are reachable from each other, and such that the cut minimises the summation of edge weights removed.
As you can tell, I'm not a maths wizard, but I need to implement this for small graphs. (Preferably in the next two hours :/). Should I be looking at something like linear programming?
Any pointers would be greatly appreciated. Thanks!
EDIT: Not a homework problem (unfortunately)… if I had had the type of education where this was a homework problem, I wouldn't need to ask now. 🙂
The background is that I have a set of equivalence relations which hold between a set of things. I can perform the transitive closure of these equivalence relations to determine equivalence classes.
However, these relations are fallible. Afterwards, I can look at an equivalence class $\{A, B, C, D, E\}$ and say hey, crap!: thing $A$ and thing $B$ are different, and thing $B$ and $C$ are different. I need to break up this equivalence class.
So, I look at the original non-transitive graph of equivalences. I want to do a minimum cut, but generally the number of vertices in the graph are small, and ties frequently occur. I want to avoid trivial decisions on what to cut. Turns out I can weight the original equivalence relations.
Given the original non-transitive weighted graph of equivalences, and the set of sets of things I know to be different, I want to perform some minimal-cut of the graph, and then reapply transitive closure over the sub-graphs.
Any help appreciated for a sleep-deprived Java hacker (even if you hate Java hackers).
Best Answer
So you want to find a minimum cost cut so that for each $I \in \mathbf{I}$, $I$ is 'cut' by the set of edges?
In general this is NP-Hard, even in the case when each $|I| = 2$ (i.e each set has exactly two elements). (I believe this is called as the multi-cut problem).
When $\mathbf{I} = \{ \{s, t\}\}$, this becomes the max-flow min-cut problem which is solvable in polynomial time.
Hope that helps.