b'@online{Krithika2307.10607,'b'\nTITLE = {Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction},\nAUTHOR = {Krithika, R. and Kutty Malu, V. K. and Sharma, Roohani and Tale, Prafullkumar},\nLANGUAGE = {eng},\nURL = {https://arxiv.org/abs/2307.10607},\nEPRINT = {2307.10607},\nEPRINTTYPE = {arXiv},\nYEAR = {2023},\nMARGINALMARK = {$\\bullet$},\nABSTRACT = {In this work, we initiate the complexity study of Biclique Contraction and<br>Balanced Biclique Contraction. In these problems, given as input a graph G and<br>an integer k, the objective is to determine whether one can contract at most k<br>edges in G to obtain a biclique and a balanced biclique, respectively. We first<br>prove that these problems are NP-complete even when the input graph is<br>bipartite. Next, we study the parameterized complexity of these problems and<br>show that they admit single exponential-time FPT algorithms when parameterized<br>by the number k of edge contractions. Then, we show that Balanced Biclique<br>Contraction admits a quadratic vertex kernel while Biclique Contraction does<br>not admit any polynomial compression (or kernel) under standard<br>complexity-theoretic assumptions.<br>},\n}\n'