The Parameterized Complexity of the k -Biclique Problem
Bingkai Lin · Journal of the ACM · 2018
Given a graph G and an integer k , the k -B iclique problem asks whether G contains a complete bipartite subgraph with k vertices on each side. Whether there is an f ( k ) ċ | G | O (1) -time algorithm, solving k -B iclique for some computable function f has been a longstanding open problem. We show that k -B iclique is W[1] -hard, which implies that such an f ( k ) ċ | G | O (1) -time algorithm does not exist under the hypothesis W[1] ≠ FPT from parameterized complexity theory. To prove this result, we give a reduction which, for every n -vertex graph G and small integer k , constructs a bipartite graph H = ( L ⊍ R , E ) in time polynomial in n such that if G contains a clique with k vertices, then there are k ( k − 1)/2 vertices in L with n θ(1/ k ) common neighbors; otherwise, any k ( k − 1)/2 vertices in L have at most ( k +1)! common neighbors. An additional feature of this reduction is that it creates a gap on the right side of the biclique. Such a gap might have further applications in proving hardness of approximation results. Assuming a randomized version of Exponential Time Hypothesis, we establish an f ( k ) ċ | G | o (√ k ) -time lower bound for k - Biclique for any computable function f . Combining our result with the work of Bulatov and Marx [2014], we obtain a dichotomy classification of the parameterized complexity of cardinality constraint satisfaction problems.