max planck institut
informatik

# MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: On the Parameterized Complexity of Biclique Cover and Partititon Davis Issac Max-Planck-Institut für Informatik - D1 AG1 Mittagsseminar (own work) D1We use this to send out email in the morning. AG Audience English
Date: Tuesday, 16 August 2016 13:00 30 Minutes Saarbrücken E1 4 024
 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}}$.
Name(s): Davis Issac