Campus Event Calendar

Event Entry

What and Who

On the Parameterized Complexity of Biclique Cover and Partititon

Davis Issac
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 16 August 2016
30 Minutes
E1 4


Given a bipartite graph $G$, we consider the decision problem called {\bc} 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 {\bp} 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 {\bp} to $O^*(2^{k^2})$ by exploiting a linear algebraic view on this problem with an algorithm using arithmetic in a finite field. On the other hand, we show that no such improvement is possible for {\bc} unless the Exponential Time Hypothesis (ETH) is false by proving a corresponding doubly exponential lower bound on the running time. We achieve this by giving a reduction from 3SAT on $n$ variables to an instance of {\bc} with $k=O(\log n)$. As a further consequence of this reduction, we show that there is no subexponential kernel for {\bc} 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 $\frac{n}{\log n}$ for both problems, which seemingly remained unnoticed by the approximation community as the best previously reported approximation factor was $\frac{n}{\sqrt{\log n}}$.


Davis Issac
--email hidden
passcode not visible
logged in users only

Davis Issac, 07/28/2016 11:59 -- Created document.