2023/07/20 by R. Krithika, V. K. Kutty Malu, Krithika, R. +5
Computer Science · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Formal Methods in Verification #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2307.10607
openalex publication_date 2023/07/20 · openalex created_date 2023/07/22 · openalex updated_date 2026/07/28
In this work, we initiate the complexity study of Biclique Contraction and Balanced Biclique Contraction. In these problems, given as input a graph G and an integer k, the objective is to determine whether one can contract at most k edges in G to obtain a biclique and a balanced biclique, respectively. We first prove that these problems are NP-complete even when the input graph is bipartite. Next, we study the parameterized complexity of these problems and show that they admit single exponential-time FPT algorithms when parameterized by the number k of edge contractions. Then, we show that Balanced Biclique Contraction admits a quadratic vertex kernel while Biclique Contraction does not admit any polynomial compression (or kernel) under standard complexity-theoretic assumptions. We also give faster FPT algorithms for contraction to restricted bicliques.