6
$\begingroup$

I have a bipartite graph $G = (U,V,E)$, where $U$ and $V$ are disjoint node sets and $U \cup V$ is the set of all vertices, and $E$ is the set of all edges. I'm looking for subsets $U' \subseteq U$ and $V' \subseteq V$ such that there exists an edge $\{i,j\} \in E$ for all $i \in U', j \in V'$ and $|U'| + |V'|$ is maximum.

Ideally, I'm looking for the absolute best solution (a single one is sufficient if there is more than one), but happy to find any solution so that $U'$ contains at least 50% of $U$ and $V'$ contains at least 50% of $V$ (and no solution if no such solution exists).

The naive algorithm (construct all subsets, calculate if they satisfy the requirements and pick the largest) does not seem very promising to find a quick solution.

I'm not that familiar with the terms in graph theory, so I'll be perfectly happy with references to "standard problems" if that's what I'm looking for.

$\endgroup$
  • 2
    $\begingroup$ You are looking for maximal complete bipartite subgraph - it looks like the problem is NP-complete. Also please see: stackoverflow.com/questions/15699714/… $\endgroup$ – HEKTO Nov 23 '15 at 15:24
  • 1
    $\begingroup$ Maximizing the number of edges is NP-complete, but maximizing the number of vertices is polynomially solvable (see my answer). I'd say this isn't a duplicate because the SO question asks to list all cliques, while this one deals with finding just a maximal one. $\endgroup$ – Tom van der Zanden Nov 23 '15 at 15:47
  • $\begingroup$ @HEKTO MaxiMUM. A maximal complete bipartite subgraph is merely one that can't be made bigger by adding more vertices; a maximum one is one of biggest possible size. $\endgroup$ – David Richerby Nov 23 '15 at 20:13
  • $\begingroup$ @DavidRicherby - of course! Thank you $\endgroup$ – HEKTO Nov 23 '15 at 20:45
6
$\begingroup$

Rephrasing from On Bipartite and Multipartite Clique Problems:

You can formulate the problem as an Integer Linear Program. Let the vertices in each partition be $V_1,V_2$ respectively. Take a (binary) variable $x_v$ for each $v\in V_1\cup V_2$. Then the problem is do determine

$$\textrm{maximize } \Sigma_{v\in V_1\cup V_2} x_v \textrm{ subject to}$$

$$x_v+x_u\leq 1 \textrm{ for all } u\in V_1, v\in V_2 \textrm{ so that } (u,v)\notin E$$

In general, solving ILP's is $NP$-complete. However, in this case, the corresponding constraint matrix is totally unimodular. Consider the relaxed problem: instead of requiring all $x_v$ to be binary, we instead only require that $0\leq x_v\leq 1$ (dropping the integrality constraint). Because the constraint matrix is totally unimodular, the optimal solution to the LP will be integral (and thus also a solution for the ILP). You can use the simplex method (or if you insist on wost-case polynomial time, the ellipsoid method) to obtain a solution for the LP, which is automatically a solution for the ILP.

$\endgroup$
  • $\begingroup$ "Because the constraint matrix is totally unimodular, the optimal solution to the LP will be integral" -- that is very cool, and you make it seem that it is standard in (I)LP theory. I've never heard of the criterion before. $\endgroup$ – Raphael Nov 23 '15 at 19:36
  • 1
    $\begingroup$ @Raphael It is quite standard. It's somewhat similar to (and a generalization of) how maximum flows always have integral solutions (if you have integral capacities). $\endgroup$ – Tom van der Zanden Nov 23 '15 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.