Obtaining a Bipartite Graph by Contracting Few Edges

Pinar Heggernes, Van 'T Hof, Pim, Daniel Lokshtanov & Christophe Paul
We initiate the study of the Bipartite Contraction problem from the perspective of parameterized complexity. In this problem we are given a graph G on n vertices and an integer k, and the task is to determine whether we can obtain a bipartite graph from G by a sequence of at most k edge contractions. Our main result is an f(k) n^{O(1)} time algorithm for Bipartite Contraction. Despite a strong resemblance between Bipartite Contraction and...