Stanislaw Bylka

LOCAL IMPROVING ALGORITHMS FOR LARGEST BIPARTITE SUBGRAPHS

808

Abstract

Bondy and Locke [JGT 10] present a polynomial algorithm which works only on triangle-free graphs with maximum degree three. Their algorithm returns a bipartite subgraph containing at least 4/5 of edges. We propose some "local switching" search algorithms for finding bipartite subgraphs of a given graph. Using a vertex and some its neighbours as a switching we define, indexed by two natural numbers (n,m), the class algorithms to improve a given bipartition. For the special case of connected graphs with maximum degree three, the worst-case behaviour of the (2,2)-algorithm is established. This algorithm obtains the lower bound 3/4 of edges on pendant triangle free graphs with maximum degree three. We show that (n,m)-algorithms do not obtain the lower bound 4/5 even the graph is 3-regular and triangle free. We prove that an local switching search algorithm (which three-stars-substructures take in order to improve a given bipartition) obtains the lower bound 7/9 if the graph is 3-regular. The proofs of the results use various tricky applications of switching for small sets.