4
$\begingroup$

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

  • 1
    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.2010-10-10

2 Answers 2

1

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.

  • 0
    Yep, I believe you're correct with the NP-hardness.2010-10-12
0

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