Students will identify certain students they want to work with. I have therefore decided to split them into two groups where I want to minimize the number of people in Group 1 who want to work with students from Group 2.

I was thinking about creating a source node s, and creating a node for each person ($p_i$) - followed by hooking up the s to each $p_i$. Then I would create, another series of nodes for each person ($q_i$) and hook up each $p_i$ to each $q_i$ if $p_i$ doesn't want to work with $q_i$. Then, I would hook up each $q_i$ to a terminal node t. Each of the edges would have weight 1.

I was thinking about running Edmonds–Karp on it. Now, the solution would yield the maximum bipartite matching of the group (see e.g. here). For each active arc from $p_i$ to $q_i$ in the final diagram, I would separate those two students.

However, I have a bad taste in my mouth after running this algorithm; the bad taste stems from modeling the instance with respect to my intention: If I maximize the complement (the desire not to work with someone), do I really minimize the desire of students to work with each other across the two groups?

If my hunch is correct (in that I'm wrong), please point me in the right direction.

  • 5
    $\begingroup$ This title is disturbing. $\endgroup$
    – Raphael
    Apr 9 '14 at 7:12

It sounds like you have properly reduced the maximum bipartite matching problem to the maximum flow problem, all you need is the reasoning to convince yourself why it is true. You are worried about the complement, so let's consider that. Remember that there is a duality among the minimum cut problem and the maximum flow problem so in finding the minimum cut you will equivalently find the maximum flow. For the definition of minimum cut:

a partition of the vertices of a graph into two disjoint subsets that are joined by at least one edge whose cut set has the smallest number of edges (unweighted case) or smallest sum of weights possible. Several algorithms exist to find minimum cuts.

The minimum cut for the graph you have constructed will have the smallest number of edges since all the weights are uniform and therefore the smallest number of people from the two sets who want to work togethers given that:

$w(p_i, q_j) = 1 \Leftrightarrow$ person $p_i$ does not want to work with person $q_j$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.