Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

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)
What and Who
Title:On the Parameterized Complexity of Biclique Cover and Partititon
Speaker:Davis Issac
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 16 August 2016
Duration:30 Minutes
Building: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}}$.
Name(s):Davis Issac
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Created by:Davis Issac, 07/28/2016 11:59 AMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Davis Issac, 07/28/2016 11:59 AM -- Created document.