The parameterized complexity of k-Biclique

Given a graph G and a parameter k, the k-Biclique problem asks whether G contains a complete bipartite subgraph Kk,k. This is one of the most easily stated problems on graphs whose parameterized complexity has been long unknown. We prove that k-Biclique is W[1]-hard by giving an fpt-reduction from k-Clique to k-Biclique, thus solving this longstanding open problem. Our reduction uses a class of bipartite graphs with a certain threshold property, which might be of some independent interest. More precisely, for positive in-tegers n, s and t, we consider a bipartite graph G = (A ∪ ̇ B,E) such that A can be partitioned into A = V1 ∪ ̇ V2 ∪̇, · · · , ∪ ̇ Vn and for every s distinct indices i1, · · · , is, there exist vi1 ∈ Vi1, · · · , vis ∈ Vis such that vi1, · · · , vis have at least t+ 1 common neighbors in B; on the other hand, every s+1 distinct vertices in A have at most t common neighbors in B. We prove that given such threshold bipartite graphs, we can construct an fpt-reduction from k-Clique to k-Biclique. Using the Paley-type graphs and Weil’s character sum theorem, we show that for t = (s+1)! and n large enough, such threshold bipartite graphs can be computed in polynomial time. One corol-lary of our reduction is that there is no f(k) ·no(k) time algorithm to decide whether a graph contains a sub-graph isomorphic to Kk!,k! unless the Exponential Time Hypothesis (ETH) fails. We also provide a probabilistic construction with better parameters t = Θ(s2), which indicates that k-Biclique has no f(k) · no( k)-time al-gorithm unless 3-SAT with m clauses can be solved in 2o(m)-time with high probability. Besides the lower bound for exact computation of k-Biclique, our result also implies a dichotomy classification of the parame-terized complexity of cardinality constraint satisfaction problems and the inapproximability of the maximum k-intersection problem