7
$\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$
4
  • 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, 2015 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$ Nov 23, 2015 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$ Nov 23, 2015 at 20:13
  • $\begingroup$ @DavidRicherby - of course! Thank you $\endgroup$
    – HEKTO
    Nov 23, 2015 at 20:45

1 Answer 1

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$
2
  • $\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, 2015 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$ Nov 23, 2015 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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