Weakly Bipartite Graphs and the Max-Cut Problem

摘要

Weakly bipartite graphs, a class which includes bipartite and planar graphs, are introduced. They are so-named because their bipartite subgraph polytrope coincides with a certain polyhedron related to odd cycle constraints. It is shown that the max-cut problem can be solved in polynomial time for weakly bipartite graphs. The polynomial algorithm presented is based on the ellipsoid method and on an algorithm computing a shortest path of even length. Although a method for computing a minimum weight odd cycle in a graph in polynomial time is revealed, research to determine whether it is possible to find an odd hole in polynomial time is recommended.