On the Parameterized Complexity of Biclique Cover and Partition

Authors Sunil Chandran, Davis Issac, Andreas Karrenbauer



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2016.11.pdf
  • Filesize: 0.59 MB
  • 13 pages

Document Identifiers

Author Details

Sunil Chandran
Davis Issac
Andreas Karrenbauer

Cite AsGet BibTex

Sunil Chandran, Davis Issac, and Andreas Karrenbauer. On the Parameterized Complexity of Biclique Cover and Partition. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.IPEC.2016.11

Abstract

Given a bipartite graph G, we consider the decision problem called BicliqueCover for a fixed positive integer parameter k where we are asked whether the edges of G can be covered with at most k complete bipartite subgraphs (a.k.a. bicliques). In the BicliquePartition problem, we have the additional constraint that each edge should appear in exactly one of the k bicliques. These problems are both known to be NP-complete but fixed parameter tractable. However, the known FPT algorithms have a running time that is doubly exponential in k, and the best known kernel for both problems is exponential in k. We build on this kernel and improve the running time for BicliquePartition to O*(2^{2k^2+k*log(k)+k}) by exploiting a linear algebraic view on this problem. On the other hand, we show that no such improvement is possible for BicliqueCover unless the Exponential Time Hypothesis (ETH) is false by proving a doubly exponential lower bound on the running time. We achieve this by giving a reduction from 3SAT on n variables to an instance of BicliqueCover with k=O(log(n)). As a further consequence of this reduction, we show that there is no subexponential kernel for BicliqueCover unless P=NP. Finally, we point out the significance of the exponential kernel mentioned above for the design of polynomial-time approximation algorithms for the optimization versions of both problems. That is, we show that it is possible to obtain approximation factors of n/log(n) for both problems, whereas the previous best approximation factor was n/sqrt(log(n)).
Keywords
  • Biclique Cover/Partition
  • Linear algebra in finite fields
  • Lower bound

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Parinya Chalermsook, Sandy Heydrich, Eugenia Holm, and Andreas Karrenbauer. Nearly Tight Approximability Results for Minimum Biclique Cover and Partition. In Algorithms - ESA 2014, volume 8737 of LNCS, pages 235-246. Springer Berlin Heidelberg, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_20.
  2. Marek Cygan, Marcin Pilipczuk, and Michał Pilipczuk. Known algorithms for edge clique cover are probably optimal. SIAM Journal on Computing, 45(1):67-83, 2016. URL: http://dx.doi.org/10.1137/130947076.
  3. Alina Ene, William Horne, Nikola Milosavljevic, Prasad Rao, Robert Schreiber, and Robert E. Tarjan. Fast exact and heuristic methods for role minimization problems. In SACMAT'08: Proceedings of the 13th ACM symposium on Access control models and technologies, pages 1-10, New York, NY, USA, 2008. ACM. URL: http://dx.doi.org/10.1145/1377836.1377838.
  4. David Eppstein, Michael T. Goodrich, and Jeremy Yu Meng. Confluent layered drawings. Algorithmica, 47:439-452, 2007. URL: http://dx.doi.org/10.1007/s00453-006-0159-8.
  5. Peter C. Fishburn and Peter L. Hammer. Bipartite dimensions and bipartite degrees of graphs. Discrete Math., 160(1-3):127-148, 1996. URL: http://dx.doi.org/10.1016/0012-365X(95)00154-O.
  6. Herbert Fleischner, Egbert Mujuni, Daniël Paulusma, and Stefan Szeider. Covering graphs with few complete bipartite subgraphs. TCS, 410(21-23):2045-2053, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2008.12.059.
  7. Floris Geerts, Bart Goethals, and Taneli Mielikäinen. Tiling databases. In Discovery Science, pages 278-289. Springer, 2004. Google Scholar
  8. David A. Gregory, Norman J. Pullman, Kathryn F. Jones, and J. Richard Lundgren. Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices. J. Comb. Theory, Ser. B, 51(1):73-89, 1991. URL: http://dx.doi.org/10.1016/0095-8956(91)90006-6.
  9. Hermann Gruber and Markus Holzer. Inapproximability of Nondeterministic State and Transition Complexity Assuming P≠NP. In Tero Harju, Juhani Karhumäki, and Arto Lepistö, editors, Developments in Language Theory, volume 4588 of Lecture Notes in Computer Science, pages 205-216. Springer, 2007. URL: http://dx.doi.org/10.1007/978-3-540-73208-2_21.
  10. Tao Jiang and B. Ravikumar. Minimal NFA Problems are Hard. SIAM Journal on Computing, 22(6):1117-1141, 1993. URL: http://dx.doi.org/10.1137/0222067.
  11. Dana S. Nau, George Markowsky, Max A. Woodbury, and D. Bernard Amos. A mathematical analysis of human leukocyte antigen serology. Math. Biosciences, 40(3-4):243-270, 1978. URL: http://dx.doi.org/10.1016/0025-5564(78)90088-3.
  12. Igor Nor, Danny Hermelin, Sylvain Charlat, Jan Engelstadter, Max Reuter, Olivier Duron, and Marie-France Sagot. Mod/Resc parsimony inference: Theory and application. Inf. Comput., 213:23-32, 2012. URL: http://dx.doi.org/10.1016/j.ic.2011.03.008.
  13. James Orlin. Contentment in graph theory: Covering graphs with cliques. Indagationes Mathematicae (Proceedings), 80(5):406-424, 1977. URL: http://dx.doi.org/10.1016/1385-7258(77)90055-5.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail