Minimum weight bipartite graph clique covering

2012-09-16T19:34:22Z

I was wondering if anyone here could give me any pointers as to how to solve the following problem.

Let $B=(L,R,E)$ be a bipartite graph, and $\forall u\in L\cup R$, let $c_u$ be a cost associated to $u$. The problem is to find a set of bicliques covering $B$ of minimum weight, ie $\{K_i\}$ s.t. $\sum_i \sum_{u \in K_i} c_u$ is minimal, and $K_i$ is a biclique of $B$.

To clarify what I mean by covering: all vertices and edges should belong to at least one $K_i$, and conversely all edges (and vertices) in each of the $K_i$ should be present in the original bipartite graph $B$. In other words, $\{K_i\}$ can be considered as an encoding of $B$ in terms of (overlapping) bicliques.

My intuition is that it's NP-Hard. If that is the case, any idea of what would be the best way to approximate the result (ie a biclique covering of $B$ of low enough weight) ?

Edit: Here is an example, consider the following bipartite graph:

A -- 1
A -- 2
B -- 1
B -- 2
B -- 3
C -- 2
C -- 3

And the set of weights $c_A = 2, c_B = 1, c_C = 2, c_1 = 1, c_2 = 1, c_3 = 1$

Here is a set of covering bicliques:

(B) (1, 2, 3) [weight = 1+1+1+1 = 4]
(A) (1, 2)    [weight = 2+1+1   = 4]
(C) (2, 3)    [weight = 2+1+1   = 4]
-- total weight = 12

And here is a covering with smaller weight:

(A, B) (1, 2) [weight = 2+1+1+1 = 5]
(B, C) (2, 3) [weight = 2+1+1+1 = 5]
-- total weight = 10

Additional question: What if the weight function is defined as $\sum_i \left( \alpha + \sum_{u \in K_i} c_u\right)$, that is adding a constant cost for each biclique? This is in fact the real question I'm interested in, basically an answer to this question would allow an efficient compression of the representation of the bipartite structure.

More updates: Per Containment in graph Theory : Covering graphs with cliques, the second version of the problem is NP-hard: the case where $\alpha = 1$ and $c_u = 0$ is COVERING BY COMPLETE BIPARTITE SUBGRAPHS, which was shown to be NP-complete by Orlin. Could not find any approximation scheme though.

Answer by Adrien Friggeri for How do researchers carry out computational experiments in Graph Theory?

2010-06-16T03:00:34Z

If you are not limited to java/c++/matlab and know python, you should take a look at networkx, it's pretty complete.

Comment by Adrien Friggeri

2012-09-17T16:37:07Z

Edited to add complexity of the second part of the question.

Comment by Adrien Friggeri

2012-09-17T06:27:17Z

I edited the question to clarify what I mean by "covering"

User adrien friggeri - MathOverflow

Minimum weight bipartite graph clique covering

Answer by Adrien Friggeri for How do researchers carry out computational experiments in Graph Theory?

Comment by Adrien Friggeri

Comment by Adrien Friggeri