  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.
