Selecting minimum number of vertices in set U of a bipartite graph to cover at least a certain number of vertices in set V

Question

I have a bipartite graph G = (U, V, E) which is a graph whose vertices are divided into two disjoint sets of U and V, such that every edge in E connects a vertex in U to a vertex in V. I translate an edge to a “covering”, i.e. an edge (u,v) means that vertex u can cover vertex v.

A vertex in U can cover more than one vertex in V and a vertex in V can be covered by more than one vertex in U.

I want to find the minimum set of vertices (min cardinality) in U to cover at least s vertices in V, such that s is an integer and 0 < s < |V|. It is fine if a vertex in V is covered by more than one vertices in such a minimum set.

If we also consider weights for edges, can we find such a minimum set of vertices, guaranteeing that those vertices have the maximum sum of weights for their outgoing edges (maximum covering)? I mean, if there is more than one such minimum set of vertices (all with the same cardinality), can we find the minimum set with maximum cardinality? Or at least, can we find all those minimum sets to filter the one with maximum outgoing weight later?

Answer 1

So this problem is NP-hard, by reduction from set cover (the requirement that s < |V| is a bit of a speed bump, but we can duplicate each vertex in V and set s = 2 |V| - 1).

In practice you can tackle this problem with integer programming. The integer program looks like this:

0-1 variables x_u for u in U; x_u = 1 means that u is selected
0-1 variables y_v for v in V; y_v = 1 means that v is covered

minimize sum_{u in U} x_u
subject to
sum_{v in V} y_v ≥ s
for each v in V,  y_v ≤ sum_{u in U such that u covers v} x_u

For the weighted version, first solve the unweighted version to find the optimum objective (let's call it k). Then add a new constraint and solve for a new objective:

0-1 variables x_u for u in U; x_u = 1 means that u is selected
0-1 variables y_v for v in V; y_v = 1 means that v is covered

minimize sum_{u in U} x_u (sum_{v in V such that u covers v} weight(uv))
subject to
sum_{u in U} x_u ≤ k
sum_{v in V} y_v ≥ s
for each v in V,  y_v ≤ sum_{u in U such that u covers v} x_u

You'll need a MIP solver library such as OR-Tools.