AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

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