Search code examples
algorithmgraphbipartiteminimum-cut

Looking for algorithms: Minimum cut to produce bipartite graph

Given an undirected weighted graph (or a single connected component of a larger disjoint graph) which typically will contain numerous odd and even cycles, I am searching for algorithms to remove the smallest possible number of edges necessary in order to produce one or more bipartite subgraphs. Are there any standard algorithms in the literature such as exist for minimum cut, etc.?

The problem I am trying to solve looks like this in the real world: Presentations of about 1 hour each are given to students about different subjects in one or two time blocks. Students can sign up for at least one presentation of their choice, or two, or three (3rd choice is an alternative in case one of the others isn't going to be presented). They have to be all different choices. If there are less than three sign-ups for a given presentation, it will not be given. If there are 18 or more, it will be given twice in both blocks. I have to schedule the presentations such that the maximum number of sign-ups are satisfied.

Scheduling is trivial in the following cases:

  1. Sign-ups for only one presentation can always be satisfied if the presentation is given (i.e. sign-ups >= 3);

  2. Sign-ups for two given presentations are always satisfiable if at least one of them is given twice.

First, all sign-ups are aggregated to determine which ones are given once and which are given twice. If a student has signed up for a presentation with too few other sign-ups, the alternative presentation is chosen if it will also be given.

At the end of the day, I am left with an undirected weighted graph where the vertices are the presentations and the edges represent students who have signed up for that combination of presentations, each of which is only presented once. The weight corresponds to the number of sign-ups for the unique combination of presentations (thus avoiding parallel edges).

If the number of vertices, or presentations, is around 20 or less, I have come up with a brute force solution which finishes in acceptable time. However, each additional vertex will double the runtime of that solution. After 28 or so, it rapidly becomes unmanageable.

This year we had 37 presentations, thirty of which were only given once and thus ended up in the graph. What I am trying right now for larger graphs is the following:

  1. Find all discrete components and solve each component individually;
  2. For each component, remove leaf nodes and bridge edges recursively;
  3. Generate a spanning tree (I am using Kruskal's algorithm which works very well), saving the removed edges;
  4. Generate the fundamental cycle set by adding one removed edge back into the tree at a time and stripping off the rest of the tree;
  5. Using the Gibbs-Welch algorithm, I generate the complete set of all elemental cycles starting with the fundamental set obtained in step 4;
  6. Count the number of odd and even cycles to which each edge belongs;
  7. Create a priority queue of edges (ordering discussed below) and remove each edge successively from its connected component until the resulting component is bipartite.

I cannot find an ordering of the priority queue for which I can prove that the result would be as acceptable as a solution obtained using the brute force method (it is probably NP-hard). However, I am trying something along these lines:

a. If the edge belongs only to odd cycles, remove it first;

b. If the edge belongs to more odd than even cycles, remove it before any other edges which belong to more even cycles than odd;

c. Edges with the smallest weight should be removed first.

If an edge belongs to both an odd and an even cycle, removing it would leave a larger odd cycle behind. That is why I am ordering them like that. Obviously, the larger the number of odd cycles to which an edge belongs, the higher the priority, but only if less even cycles are affected.

There are additional criteria which exist but need to be considered outside of the graph problem; for example, removing an edge effectively removes one of the sign-ups for one of the presentations, so an eye has to be kept on not letting the number of sign-ups get too small.

(EDIT: there is also the possibility of splitting presentations into two blocks which have almost enough sign-ups, e.g. 15-16 instead of 18. But this means that whoever is giving the presentation would have to do it twice, so it is a trade-off.)

Thanks in advance for any suggestions!

Solution

  • This problem is equivalent to the NP-hard weighted max cut problem, which asks for a partition of the vertices into two parts such that the maximum number of edges go between the parts.

    I think the easiest way to solve a problem size such as you have would be to formulate it as a quadratic integer program and then apply an off the shelf solver. The formulation looks like

    maximize (1/2) sum_{ij} w_{ij} (1 - y_i y_j)
subject to
y_i in {±1} for all i

    where w_ij is the weight of the undirected edge ij if present else zero (so the corresponding variable and its constraint can be omitted).