License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2016.11
URN: urn:nbn:de:0030-drops-69293
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6929/
Chandran, Sunil ;
Issac, Davis ;
Karrenbauer, Andreas
On the Parameterized Complexity of Biclique Cover and Partition
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)).
BibTeX - Entry
@InProceedings{chandran_et_al:LIPIcs:2017:6929,
author = {Sunil Chandran and Davis Issac and Andreas Karrenbauer},
title = {{On the Parameterized Complexity of Biclique Cover and Partition}},
booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
pages = {11:1--11:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-023-1},
ISSN = {1868-8969},
year = {2017},
volume = {63},
editor = {Jiong Guo and Danny Hermelin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6929},
URN = {urn:nbn:de:0030-drops-69293},
doi = {10.4230/LIPIcs.IPEC.2016.11},
annote = {Keywords: Biclique Cover/Partition, Linear algebra in finite fields, Lower bound}
}
|
Keywords: |
|
Biclique Cover/Partition, Linear algebra in finite fields, Lower bound |
|
Collection: |
|
11th International Symposium on Parameterized and Exact Computation (IPEC 2016) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
09.02.2017 |
