User adrien friggeri - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T15:51:10Z http://mathoverflow.net/feeds/user/6831 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/107341/minimum-weight-bipartite-graph-clique-covering Minimum weight bipartite graph clique covering Adrien Friggeri 2012-09-16T19:34:22Z 2012-09-17T16:36:46Z <p>I was wondering if anyone here could give me any pointers as to how to solve the following problem.</p> <p>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, <em>ie</em> $\{K_i\}$ s.t. $\sum_i \sum_{u \in K_i} c_u$ is minimal, and $K_i$ is a biclique of $B$.</p> <p>To clarify what I mean by covering: all vertices <strong>and</strong> 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.</p> <p>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 (<em>ie</em> a biclique covering of $B$ of low enough weight) ?</p> <p><strong>Edit:</strong> Here is an example, consider the following bipartite graph:</p> <pre><code>A -- 1 A -- 2 B -- 1 B -- 2 B -- 3 C -- 2 C -- 3 </code></pre> <p>And the set of weights $c_A = 2, c_B = 1, c_C = 2, c_1 = 1, c_2 = 1, c_3 = 1$</p> <p>Here is a set of covering bicliques:</p> <pre><code>(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 </code></pre> <p>And here is a covering with smaller weight:</p> <pre><code>(A, B) (1, 2) [weight = 2+1+1+1 = 5] (B, C) (2, 3) [weight = 2+1+1+1 = 5] -- total weight = 10 </code></pre> <p><strong>Additional question</strong>: 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.</p> <p><strong>More updates</strong>: Per <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.164.2412" rel="nofollow">Containment in graph Theory : Covering graphs with cliques</a>, 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.</p> http://mathoverflow.net/questions/26231/how-do-researchers-carry-out-computational-experiments-in-graph-theory/28339#28339 Answer by Adrien Friggeri for How do researchers carry out computational experiments in Graph Theory? Adrien Friggeri 2010-06-16T03:00:34Z 2010-06-16T03:00:34Z <p>If you are not limited to java/c++/matlab and know python, you should take a look at <a href="http://networkx.lanl.gov/" rel="nofollow">networkx</a>, it's pretty complete.</p> http://mathoverflow.net/questions/107341/minimum-weight-bipartite-graph-clique-covering Comment by Adrien Friggeri Adrien Friggeri 2012-09-17T16:37:07Z 2012-09-17T16:37:07Z Edited to add complexity of the second part of the question. http://mathoverflow.net/questions/107341/minimum-weight-bipartite-graph-clique-covering Comment by Adrien Friggeri Adrien Friggeri 2012-09-17T06:27:17Z 2012-09-17T06:27:17Z I edited the question to clarify what I mean by &quot;covering&quot;