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.

Minimum weight bipartite graph clique covering - MathOverflow

Minimum weight bipartite graph clique covering