Noon lecture

On 02.05.2019 at 12:30 in S6, there is the following noon lecture:

Covering and Partitioning Edges with Complete Bipartite Subgraphs

Abstract

The talk is mainly based on a work together with Sunil Chandran and Andreas Karrenbauer published at IPEC 2016.

I will talk about the problems Biclique Cover and Biclique Partition and also about some related problems. A Biclique is nothing but a complete bipartite subgraph. In biclique cover, we are given a graph and an integer \$k\$, and we want to find whether we can cover all the edges of the graph with at most \$k\$ bicliques. In biclique partition, we want to partition the edges into at most \$k\$ bicliques.

We will focus mainly on the parameterized complexity of these problems, especially focusing on the case of bipartite graphs, as bicliques in bipartite graphs capture the idea of "combinatorial rectangles", which occur naturally in many applications. I will also demonstrate the equivalence of these problems to some matrix factorization problems.

I will show an algorithm with \$O(2^{k^2})poly(n)\$ running time for biclique partition. The best previously known fixed parameter running time for the problem was \$O(2^{2^k}poly(n)\$. Our algorithm makes use of a linear algebraic formulation of the problem and uses basic linear algebraic ideas. For biclique cover, we show that it is not possible to get running times that are better than doubly exponential in terms of k, assuming the Exponential time hypothesis. We also show that there is no sub-exponential size kernel in terms of \$k\$ for biclique cover unless \$P=NP\$. We achieve these two results by giving a reduction from 3SAT on \$n\$ variables to an instance of biclique cover with \$k=O(\log n)\$. I will give a high level overview of this reduction in the talk.

I will conclude by pointing out some interesting open problems on the topic.

Webmaster: kamweb.mff.cuni.cz         Modified: 25. 02. 2019