How can I find a non-perfect bipartite matching of a graph?

Question

That is, how can I find a bipartite matching of a graph where some vertices may not be connected to any other vertices?

EDIT: One more condition, suppose the edges are also weighted, and I'd like a matching such that the total edge weight is minimized (or maximized).

Answer 1

First, I'm going to assume your weights are nonnegative.

In your edited version, you're talking about the assignment problem: n agents are each assigned a unique action to perform, where each agent has an arbitrary non-negative cost for each action. Though this description is for perfect bipartite matching, you can perform a couple of tricks. To balance out the sides, you can add vertices that have weight 0 to everything on the other side, to say that there is 0 cost associated with taking no action / an action not taken. Missing links can be modeled by a cost exceeding the sum of all true costs, so they will only be selected if the problem is not solvable. For your edited version, I would use the Hungarian Algorithm. Finally, this problem is also known as "maximum weighted bipartite matching" and another reference to algorithms can be found in the second paragraph under maximum matchings in bipartite graphs.

EDIT: if you want to maximize cost rather than minimize it, you have to flip your costs around. Just find the maximum cost and subtract each cost from the maximum. Then you won't want to take any cost 0 links if you had missing links.

Answer 2

Use Hopcroft-Karp algorithm, it does exactly what you want.