×
Lin, Bingkai

The parameterized complexity of the \(k\)-biclique problem. (English) Zbl 1426.68131

J. ACM 65, No. 5, Article No. 34, 23 p. (2018).

Cited in 16 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R10 Graph theory (including graph drawing) in computer science

Keywords:

biclique; exponential time hypothesis; maximum \(k\)-subset intersection; Weil’s character sum theorem; dichotomy theorem; parameterized inapproximability; probabilistic method

Citations:

Zbl 1360.68499
Cite Review PDF
Full Text: DOI

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.
[2] Noga Alon, Raphael Yuster, and Uri Zwick. 1995. Color-coding. J. ACM 42, 4 (1995), 844-856. · Zbl 0885.68116
[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. · Zbl 1223.68043
[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. · Zbl 1028.68065
[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. · Zbl 1357.68077
[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. · Zbl 0915.05076
[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. · Zbl 1259.05160
[8] Hans L. Bodlaender. 1994. A tourist guide through treewidth. Acta Cybernetica 11, 1-2 (1994), 1. · Zbl 0804.68101
[9] Andrei A. Bulatov and Dániel Marx. 2014. Constraint satisfaction parameterized by solution size. SIAM J. Comput. 43, 2 (2014), 573-616. · Zbl 1360.68499
[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. · Zbl 1154.68570
[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. · Zbl 1192.68313
[12] Yijia Chen, Martin Grohe, and Magdalena Grüber. 2006. On parameterized approximability. In Parameterized and Exact Computation. Springer, 109-120. · Zbl 1154.68571
[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. · Zbl 1243.68185
[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.
[17] Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity, Vol. 4. Springer. · Zbl 1358.68006
[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. · Zbl 1154.68572
[19] Paul Erdős. 1934. A Theorem of Sylvester and Schur. J. London Mathematical Society s1-9 (4) (1934), 278-282. · Zbl 0010.10302
[20] Paul Erdős. 1959. Graph theory and probability. Canad. J. Math 11 (1959), 34-38. · Zbl 0084.39602
[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. · Zbl 1192.68358
[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). · Zbl 1205.05087
[23] Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer Verlag, Berlin. · Zbl 1143.68016
[24] Serge Gaspers, Dieter Kratsch, and Mathieu Liedloff. 2012. On independent sets and bicliques in graphs. Algorithmica 62, 3-4 (2012), 637-658. · Zbl 1239.05101
[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. · Zbl 1312.68101
[26] Russell Impagliazzo and Ramamohan Paturi. 2001. On the complexity of k-SAT. J. Comput. System Sci. 62 (2001), 367-375. · Zbl 0990.68079
[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.
[28] David S. Johnson. 1987. The NP-completeness column: An ongoing guide. J. of Algorithms 8, 3 (1987), 438-448. · Zbl 0633.68022
[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. · Zbl 1127.68035
[30] Ton Kloks. 1994. Treewidth: Computations and Approximations, Vol. 842. Springer Science 8 Business Media. · Zbl 0825.68144
[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. · Zbl 0858.05061
[32] Konstantin Kutzkov. 2012. An exact exponential time algorithm for counting bipartite cliques. Inform. Process. Lett. 112, 13 (2012), 535-539. · Zbl 1243.05227
[33] Rudolf Lidl and Harald Niederreiter. 1997. Finite Fields, Vol. 20. Cambridge University Press. · Zbl 0866.11069
[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.
[35] Dániel Marx. 2008. Parameterized complexity and approximation algorithms. Comput. J. 51, 1 (2008), 60-78.
[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. · Zbl 0611.05017
[38] Wolfgang M. Schmidt. 1976. Equations over Finite Fields an Elementary Approach (Lecture Notes in Mathematics Volume 536). Springer, Berlin. · Zbl 0329.12001
[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.
[40] Eduardo C. Xavier. 2012. A note on a maximum k-subset intersection problem. Inform. Process. Lett. 112, 12 (2012), 471-472. · Zbl 1243.68189
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.