The Parameterized Complexity of the k -Biclique Problem
Author:
Open Access
- 29 August 2018
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 65 (5) , 1-23
Abstract
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.Keywords
Funding Information
- JSPS KAKENHI (JP16H07409)
- JST ERATO (JPMJER1201)
This publication has 31 references indexed in Scilit:
- An exact exponential time algorithm for counting bipartite cliquesInformation Processing Letters, 2012
- A note on a Maximum k-Subset Intersection problemInformation Processing Letters, 2012
- On Independent Sets and Bicliques in GraphsAlgorithmica, 2010
- Parameterized Complexity and Approximation AlgorithmsThe Computer Journal, 2007
- The complexity of homomorphism and constraint satisfaction problems seen from the other sideJournal of the ACM, 2007
- Norm-graphs and bipartite tur n numbersCombinatorica, 1996
- Color-codingJournal of the ACM, 1995
- The NP-completeness column: An ongoing guideJournal of Algorithms, 1987
- Graph minors. II. Algorithmic aspects of tree-widthJournal of Algorithms, 1986
- A Theorem of Sylvester and SchurJournal of the London Mathematical Society, 1934