# Minimum cuts for weighted graphs

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).

-
Could you provide a little more background of the motivation for this problem? Is this homework, if so for what class? Is this a personal project or a project for a class? If so, what exactly are you working on and why. The more details we have the better we can help you. Thanks! – jericson Oct 10 '10 at 4:31
Hi jericson. Hopefully my edits help get a better picture? Cheers! – badroit Oct 10 '10 at 4:45
Yes the edit gives a much clearer picture. I know of ways to analyze very very big graphs but in your case this would not be helpful. Is it possible that you can do it by hand/guess and check? I do not know about the programming option. You could try stackoverflow.com or something similar. – jericson Oct 10 '10 at 5:06
No problem. I came up with some form of solution that works quite okay. Will sketch here when I'm done deadline fighting (the deadline is winning handsomely). – badroit Oct 10 '10 at 7:34
You might want to consider asking this on cstheory.stackexchange.com. People might be able to give a name to this problem and point you to the latest approximation algorithms etc. – Aryabhata Oct 10 '10 at 14:54

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.

-
Yep, I believe you're correct with the NP-hardness. – badroit Oct 12 '10 at 14:42

Not an answer to my question, as opposed to a workaround I applied for my case.

Firstly, in my particular case, all $\lvert I \rvert = 2$ for all $I \in \mathbf{I}$.

Sketching, I applied the following:

• model the weighted graph of non-transitive, symmetric (directionless) equivalences;
• apply iterations until fixpoint as follows:
• order the edges based on edge weight (assumes a total ordering, and granular ordering such that you don't have to make trivial decisions between equals weights);
• iterate over the edges in decreasing order, and derive a "strong, transitive equivalence" for the highest weighted edge:
• merge those nodes in the graph, and their edges and edge weights;
• do not merge nodes which conflict with $\mathbf{I}$;
• do not merge nodes which have already been involved in a merge in that iteration.

Again, this is not precisely an answer to my question, but the core idea is to rebuild the equivalences in decreasing order of edge weights, avoiding any equivalences that would equate two identifiers known to be different. You might not end up with a "minimal-cut", but it's a fairly intuitive, tractable solution (which I hope makes sense).

-