snippetMinor
Bipartite Graph - How to determine largest subsets that are all connected
Viewed 0 times
graphallaresubsetsbipartitelargestthatconnecteddeterminehow
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#49878, answer score: 6
Revisions (0)
No revisions yet.