Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality Original Research Article

We propose some ‘local switching’ search algorithms for finding large bipartite subgraphs in simple undirected graphs. The algorithms are based on the ‘measure of effectiveness’ of the bipartitions of the vertex set. We analyze the worst-case behavior of these algorithms, giving general lower bounds, and also prove that the concept of switching has its limits no matter how large (fixed-size) substructures are taken in order to improve a locally optimal solution. Strengthening an early result by Edwards and Erdős, we also present two new lower bounds on the size of largest bipartite subgraphs of a graph. The first bound — involving the length of shortest odd cycles — is tight for any given girth and any number of vertices. Moreover, a corresponding bipartite subgraph can be found by a linear-time algorithm. The second bound is defined in terms of odd-degree edge-disjoint stars, and it is stronger than the Edwards-Erdős inequality whenever the graph in question contains at least two nonadjacent vertices of odd degree.