MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

From the observation, that a bipartite graph doesn't contain odd cycles, it would seem natural to attempt to destroy all odd cycles in the most efficient way, by either removing edges or vertices of odd cycles, in order to find a maximal subset of the vertices that spans a bipartite sub graph.

I would appreciate references to articles in which such direct methods of destroying odd cycles by removing edges or vertices from a graph and their related problems are discussed.

An example of a problem that is related to most effectively destroying odd cycles, would be how to determine the number of odd cycles that removing an edge or vertex will destroy.

share|cite|improve this question
This might also be of interest to you:… – Felix Goldberg Jul 28 '13 at 19:37
up vote 5 down vote accepted

This paper by Karabayashi and Reed seems to be closely related to what you are looking for.

share|cite|improve this answer
It is not quite what I hoped for, but I think it is the best I can get; thanks, Igor. – Manfred Weis Jul 28 '13 at 19:13

Not a reference, but you might enjoy tinkering with this.

Decide for your graph on two parameters C and M. For each of C-many trials, two-color the vertices. In each trial, look at the vertices v which have more neighbors of v's color than of opposite color, and allow yourself to recolor such vertices v. Perform at most M-many such recolorings. At the end of each trial, count the number n of edges that join like colored vertices. Choose the arrangement that minimizes the observed n.

There are various ways to optimize this, especially if you know the graph is 1-connected and where.

share|cite|improve this answer
@masked avenger: two coloring is indeed a good way of attacking the problem; I have already played around with some methods and also devised my own (skip-coloring), but as they do not address the very essence of the problem (namely the existence of odd cycles), I currently don't follow that thread. If you like, I can share my ideas for two-coloring approaches. – Manfred Weis Jul 29 '13 at 3:30

Meanwhile I found that the paper "Algorithm Engineering for Optimal Graph Bipartization" by Falk Hüffner is exactly what I was looking for.

The key term that is related to the problem is that of an odd cycle transversal

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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