research-article

The Parameterized Complexity of the k-Biclique Problem

Author:

Bingkai LinAuthors Info & Claims

Journal of the ACM (JACM), Volume 65, Issue 5

Article No.: 34, Pages 1 - 23

https://doi.org/10.1145/3212622

Published: 29 August 2018 Publication History

Abstract

Given a graph G and an integer k, the k-Biclique 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-Biclique for some computable function f has been a longstanding open problem.

We show that k-Biclique 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.

References

[1]

Leonard M. Adleman and Hendrik W. Lenstra. 1986. Finding irreducible polynomials over finite fields. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing. ACM, 350--355.

Digital Library

[2]

Noga Alon, Raphael Yuster, and Uri Zwick. 1995. Color-coding. J. ACM 42, 4 (1995), 844--856.

Digital Library

[3]

Christoph Ambühl, Monaldo Mastrolilli, and Ola Svensson. 2011. Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut. SIAM J. Comput. 40, 2 (2011), 567--596.

Digital Library

[4]

Sanjeev Arora. 1998. The approximability of NP-hard problems. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing. ACM, 337--348.

Digital Library

[5]

Aistis Atminas, Vadim V. Lozin, and Igor Razgon. 2012. Linear time algorithm for computing a small biclique in graphs without long induced paths. In Scandinavian Workshop on Algorithm Theory. Springer, 142--152.

Digital Library

[6]

László Babai, Anna Gál, János Kollár, Lajos Rónyai, Tibor Szabó, and Avi Wigderson. 1996. Extremal bipartite graphs and superpolynomial lower bounds for monotone span programs. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing. ACM, 603--611.

Digital Library

[7]

Daniel Binkele Raible, Henning Fernau, Serge Gaspers, and Mathieu Liedloff. 2010. Exact exponential-time algorithms for finding bicliques. Inform. Process. Lett. 111, 2 (2010), 64--67.

Digital Library

[8]

Hans L. Bodlaender. 1994. A tourist guide through treewidth. Acta Cybernetica 11, 1--2 (1994), 1.

[9]

Andrei A. Bulatov and Dániel Marx. 2014. Constraint satisfaction parameterized by solution size. SIAM J. Comput. 43, 2 (2014), 573--616.

[10]

Liming Cai and Xiuzhen Huang. 2006. Fixed-parameter approximation: Conceptual framework and approximability results. In Proceedings of the International Workshop on Parameterized and Exact Computation. Springer, 96--108.

Digital Library

[11]

Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. 2004. Linear FPT reductions and computational lower bounds. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing. ACM, 212--221.

Digital Library

[12]

Yijia Chen, Martin Grohe, and Magdalena Grüber. 2006. On parameterized approximability. In Parameterized and Exact Computation. Springer, 109--120.

Digital Library

[13]

Yijia Chen and Bingkai Lin. 2016. The constant inapproximability of the parameterized dominating set problem. In Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). 505--514.

[14]

Jean François Couturier and Dieter Kratsch. 2012. Bicolored independent sets and bicliques. Inform. Process. Lett. 112, 8 (2012), 329--334.

Digital Library

[15]

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2016. Parameterized Algorithms (1st ed.). Springer International Publishing.

[16]

Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer-Verlag.

Digital Library

[17]

Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity, Vol. 4. Springer.

Digital Library

[18]

Rodney G. Downey, Michael R. Fellows, and Catherine McCartin. 2006. Parameterized approximation problems. In Proceedings of the International Workshop on Parameterized and Exact Computation. Springer, 121--129.

Digital Library

[19]

Paul Erdős. 1934. A Theorem of Sylvester and Schur. J. London Mathematical Society s1-9 (4) (1934), 278--282.

[20]

Paul Erdős. 1959. Graph theory and probability. Canad. J. Math 11 (1959), 34--38.

[21]

Uriel Feige. 2002. Relations between average case complexity and approximation complexity. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing. ACM, 534--543.

Digital Library

[22]

Uriel Feige and Shimon Kogan. 2004. Hardness of approximation of the balanced complete bipartite subgraph problem. Dept. Comput. Sci. Appl. Math., Weizmann Inst. Sci., Rehovot, Israel, Tech. Rep. MCS04-04 (2004).

[23]

Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer Verlag, Berlin.

Digital Library

[24]

Serge Gaspers, Dieter Kratsch, and Mathieu Liedloff. 2012. On independent sets and bicliques in graphs. Algorithmica 62, 3--4 (2012), 637--658.

Digital Library

[25]

Martin Grohe. 2007. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. of the ACM (JACM) 54, 1 (2007), 1.

Digital Library

[26]

Russell Impagliazzo and Ramamohan Paturi. 2001. On the complexity of k-SAT. J. Comput. System Sci. 62 (2001), 367--375.

Digital Library

[27]

Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 1998. Which problems have strongly exponential complexity? In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998. IEEE, 653--662.

Digital Library

[28]

David S. Johnson. 1987. The NP-completeness column: An ongoing guide. J. of Algorithms 8, 3 (1987), 438--448.

Digital Library

[29]

Subhash Khot. 2006. Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36, 4 (2006), 1025--1071.

Digital Library

[30]

Ton Kloks. 1994. Treewidth: Computations and Approximations, Vol. 842. Springer Science 8 Business Media.

[31]

János Kollár, Lajos Rónyai, and Tibor Szabó. 1996. Norm-graphs and bipartite Turán numbers. Combinatorica 16, 3 (1996), 399--406.

[32]

Konstantin Kutzkov. 2012. An exact exponential time algorithm for counting bipartite cliques. Inform. Process. Lett. 112, 13 (2012), 535--539.

Digital Library

[33]

Rudolf Lidl and Harald Niederreiter. 1997. Finite Fields, Vol. 20. Cambridge University Press.

[34]

Dániel Marx. 2007. Can you beat treewidth? In 48th Annual IEEE Symposium on Foundations of Computer Science, 2007. FOCS’07. IEEE, 169--179.

Digital Library

[35]

Dániel Marx. 2008. Parameterized complexity and approximation algorithms. Comput. J. 51, 1 (2008), 60--78.

Digital Library

[36]

Srinivasa Ramanujan. 1919. A proof of Bertrand’s postulate. J. of the Indian Mathematical Society 11, 181--182 (1919), 27.

[37]

Neil Robertson and Paul D. Seymour. 1986. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 3 (1986), 309--322.

[38]

Wolfgang M. Schmidt. 1976. Equations over Finite Fields an Elementary Approach (Lecture Notes in Mathematics Volume 536). Springer, Berlin.

[39]

Igor Shparlinski. 2013. Finite Fields: Theory and Computation: The Meeting Point of Number Theory, Computer Science, Coding Theory and Cryptography, Vol. 477. Springer Science 8 Business Media.

Digital Library

[40]

Eduardo C. Xavier. 2012. A note on a maximum k-subset intersection problem. Inform. Process. Lett. 112, 12 (2012), 471--472.

Digital Library

Cited By

Deligkas AEiben EGoldsmith TDastani MSichman JAlechina NDignum V(2024)The Parameterized Complexity of Welfare Guarantees in Schelling SegregationProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662892(425-433)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662892
Guruswami VLin BRen XSun YWu KMohar BShinkar IO'Donnell R(2024)Parameterized Inapproximability Hypothesis under Exponential Time HypothesisProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649771(24-35)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649771
Bennett HCheraghchi MGuruswami VRibeiro J(2024)Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All \({\ell_{{p}}}\) NormsSIAM Journal on Computing10.1137/23M157302153:5(1439-1475)Online publication date: 7-Oct-2024
https://doi.org/10.1137/23M1573021
Show More Cited By

Index Terms

The Parameterized Complexity of the k-Biclique Problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Extremal graph theory
      2. Random graphs
2. Theory of computation
  1. Computational complexity and cryptography
    1. Problems, reductions and completeness
  2. Design and analysis of algorithms
    1. Parameterized complexity and exact algorithms
      1. W hierarchy

Recommendations

On the parameterized complexity of approximating dominating set
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

We study the parameterized complexity of approximating the k-Dominating Set (domset) problem where an integer k and a graph G on n vertices are given as input, and the goal is to find a dominating set of size at most F(k) · k whenever the graph G has a ...
The parameterized complexity of k-biclique
SODA '15: Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms

Given a graph G and a parameter k, the k-Biclique problem asks whether G contains a complete bipartite subgraph K_k,k. This is one of the most easily stated problems on graphs whose parameterized complexity has been long unknown. We prove that k-Biclique ...
On the Parameterized Complexity of Approximating Dominating Set
Distributed Computing, Algorithms and Data Structures, Algorithms, Scientific Computing, Derandomizing Algorithms, Online Algorithms and Algorithmic Information Theory

We study the parameterized complexity of approximating the k-Dominating Set (DomSet) problem where an integer k and a graph G on n vertices are given as input, and the goal is to find a dominating set of size at most F(k) ⋅ k whenever the graph G has a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 65, Issue 5

October 2018

299 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3274534

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 August 2018

Accepted: 01 April 2018

Revised: 01 October 2017

Received: 01 October 2016

Published in JACM Volume 65, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

JSPS KAKENHI
JST ERATO

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
475
Total Downloads

Downloads (Last 12 months)53
Downloads (Last 6 weeks)4

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Deligkas AEiben EGoldsmith TDastani MSichman JAlechina NDignum V(2024)The Parameterized Complexity of Welfare Guarantees in Schelling SegregationProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662892(425-433)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662892
Guruswami VLin BRen XSun YWu KMohar BShinkar IO'Donnell R(2024)Parameterized Inapproximability Hypothesis under Exponential Time HypothesisProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649771(24-35)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649771
Bennett HCheraghchi MGuruswami VRibeiro J(2024)Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All \({\ell_{{p}}}\) NormsSIAM Journal on Computing10.1137/23M157302153:5(1439-1475)Online publication date: 7-Oct-2024
https://doi.org/10.1137/23M1573021
Deligkas AEiben EGoldsmith T(2024)The Parameterized Complexity of Welfare Guarantees in Schelling SegregationTheoretical Computer Science10.1016/j.tcs.2024.114783(114783)Online publication date: Aug-2024
https://doi.org/10.1016/j.tcs.2024.114783
C.M. Gomes GLegrand-Duchesne CMahmoud RMouawad AOkamoto YF. dos Santos Vvan der Zanden T(2024)Minimum separator reconfigurationJournal of Computer and System Sciences10.1016/j.jcss.2024.103574146(103574)Online publication date: Dec-2024
https://doi.org/10.1016/j.jcss.2024.103574
Faliszewski PLackner MSornat KSzufa SElkind E(2023)An experimental comparison of multiwinner voting rules on approval electionsProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/298(2675-2683)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/298
Bennett HCheraghchi MGuruswami VRibeiro JSaha BServedio R(2023)Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ NormsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585214(553-566)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585214
Peyerimhoff NRoth MSchmitt JStix JVdovina AWellnitz P(2023)Parameterized Counting and Cayley Graph ExpandersSIAM Journal on Discrete Mathematics10.1137/22M147980437:2(405-486)Online publication date: 26-Apr-2023
https://doi.org/10.1137/22M1479804
Li FZou ZLiu XLi JYang XWang B(2023)Detecting maximum k-durable structures on temporal graphsKnowledge-Based Systems10.1016/j.knosys.2023.110561271:COnline publication date: 8-Jul-2023
https://dl.acm.org/doi/10.1016/j.knosys.2023.110561
Koana TKomusiewicz CSommer F(2023)Computing Dense and Sparse Subgraphs of Weakly Closed GraphsAlgorithmica10.1007/s00453-022-01090-z85:7(2156-2187)Online publication date: 20-Jan-2023
https://dl.acm.org/doi/10.1007/s00453-022-01090-z
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents