Bipartite selection with associated vertex cost

Question

I think I'm looking for an algorithm that can find a "minimum" "selection" in a bipartite graph. Each vertex has an associated (integer) cost to selecting it. I can only find algorithms that minimise the number of vertices in the selected set, not the cost. I'd previously thought I need a "matching", but actually I just need the subset of vertices that cover every edge...

I don't think a greedy solution can work. Suppose our sets are A, B:

Vertices 1,2,3 are in A and have cost 1. Vertex 4 is in B and has cost 2.

The solution is to remove the most expensive vertex, 4. A greedy solution that chose based on cost would fail. Similarly, if B had cost 10, we could not choose the most connected vertex greedily.

I thought of a different wording: "Given a bipartite graph where each vertex has an associated cost, find a subset of vertices of minimum cost such that every edge is incident on at least one vertex in your selected subset".

David Eisenstat David Eisenstat · Accepted Answer · 2013-04-06T13:25:08

Primal LP:

min sum_v c_v x_v
s.t.
forall e=vw. x_v + x_w >= 1
forall v. x_v >= 0

Dual LP:

max sum_e y_e
s.t.
forall v. sum_{e=vw} y_e <= c_v
forall e. y_e >= 0

Find a min cut where the edges are arcs from A to B with infinite capacity, the vertices in A are sources, and the vertices in B are sinks, with all vertices having capacity equal to their cost. (Equivalently, make a supersource with arcs to A and a supersink with arcs from B.)
Take the As that are on the "sink" side of the cut and the Bs that are on the "source" side. Every edge vw is covered because if neither v nor w belonged to the cover then vw would be residual.

Hat tip I think to Jenő Egerváry.

Bipartite selection with associated vertex cost

1 Answers