A faster FPT algorithm for Bipartite Contraction

2013/05/13 by Sylvain Guillemot, Dániel Marx, Guillemot, Sylvain +1 · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #cs.DS

paper · pdf · doi:10.48550/arxiv.1305.2743

openalex publication_date 2013/05/13 · arxiv created 2013/09/04 · arxiv updated 2013/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

The Bipartite Contraction problem is to decide, given a graph G and a parameter k, whether we can can obtain a bipartite graph from G by at most k edge contractions. The fixed-parameter tractability of the problem was shown by [Heggernes et al. 2011], with an algorithm whose running time has double-exponential dependence on k. We present a new randomized FPT algorithm for the problem, which is both conceptually simpler and achieves an improved 2^O(k2) n m running time, i.e., avoiding the double-exponential dependence on k. The algorithm can be derandomized using standard techniques.

Cited by

• A Finer View of the Parameterized Landscape of Labeled Graph Contractions
• A Single Exponential-Time FPT Algorithm for Cactus Contraction

Related

• Obtaining a Bipartite Graph by Contracting Few Edges
• A Single Exponential-Time FPT Algorithm for Cactus Contraction
• Reducing the Vertex Cover Number via Edge Contractions
• Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
• Edge Bipartization faster than 2^k