2
$\begingroup$

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.

Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ It is not quite what I hoped for, but I think it is the best I can get; thanks, Igor. $\endgroup$
    – Manfred Weis
    Commented Jul 28, 2013 at 19:13
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @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. $\endgroup$
    – Manfred Weis
    Commented Jul 29, 2013 at 3:30
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .