# How to optimally seperate a student body?

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.

• This title is disturbing. – Raphael Apr 9 '14 at 7:12

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