2026-08-05T21:18:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19381 2024-03-06T11:03:53Z ddc:004 open_access

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction Krithika, R. Malu, V. K. Kutty Sharma, Roohani Tale, Prafullkumar contraction bicliques balanced bicliques parameterized complexity A bipartite graph is called a biclique if it is a complete bipartite graph and a biclique is called a balanced biclique if it has equal number of vertices in both parts of its bipartition. 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) unless NP ⊆ coNP/poly. Schloss Dagstuhl – Leibniz-Zentrum für Informatik R. Krithika and V. K. Kutty Malu and Roohani Sharma and Prafullkumar Tale 2023 Is Part Of LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2023.8 urn:nbn:de:0030-drops-193811 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.8 eng https://creativecommons.org/licenses/by/4.0/legalcode