# Bipartite graph "matching" with multiple edges per node

I'll preface by saying that I know that the title is technically incorrect since a matching is defined such that each node has at most one edge. However I can't find the correct term so here I am

I have a matching problem that is modeled as a weighted bipartite graph with node sets $$X$$ and $$Y$$ where $$|X|\neq|Y|$$ and it can be assumed that each node in either set is connected to at least one node in the other set.

The goal is to find a (minimal) set of edges $$E$$ such that every node in the graph is the endpoint of at least one edge (i.e., $$|E|=max(|X|, |Y|)$$) while minimizing the sum of weights in $$E$$. Obviously this implies that some nodes will have more than one edge in $$E$$, in opposition to a minimum weight full matching where $$|E|=min(|X|, |Y|)$$ and some nodes may be left unmatched.

What would be the correct term to search instead of "matching" and is there an algorithm that can solve this problem?

• You write that the condition taht "every node in the graph is the endpoint of at least one edge" is the same as |E|=max(|X|,|Y|), but those things are different. The set of all edges satisfies the first condition but not the second one in general. ) Commented Feb 1, 2023 at 0:21
• @MarianoSuárez-Álvarez I've edited to clarify the implicit assumption that we want the smallest possible amount of edges (or, if that's also different, |E|=min(|X|,|Y|) is the actual condition that makes sense for my application) Commented Feb 1, 2023 at 13:15
• @Xilef11 If you want to minimize the number of edges first and the total weight only second, then you should use the strategy that begins with a maximum matching. The algorithm in my answer assumed that you want to minimize the total weight even if that means using more edges. Commented Feb 1, 2023 at 14:54

A set of edges that includes every vertex as an endpoint is called an edge cover.

In the unweighted case, finding the minimum edge cover is no harder than finding a maximum matching. In fact, we begin by finding the maximum matching; then, for every vertex that is not covered by that maximum matching, just add an arbitrary edge to cover it.

In the weighted case, things are trickier, but there is still a way to reduce it to a bipartite matching problem.

1. Take our graph $$G$$ and create a copy $$G'$$.
2. Between every vertex $$v \in V(G)$$ and its copy $$v' \in V(G')$$, add an edge; let its weight be twice the minimum weight of any edge in $$G$$ that could cover $$v$$.
3. Find a minimum-weight perfect matching $$M$$ of the graph constructed in steps 1-2. (At least one perfect matching always exists: the matching that uses all the edges $$vv'$$ created in step 2.)
4. To find an edge cover of our original graph $$G$$, combine the following. First, include all edges in $$M \cap E(G)$$. Second, for every edge in $$M$$ of the form $$vv'$$, include the cheapest edge in $$G$$ covering $$v$$ (the one used to determine the cost of $$vv'$$) in the edge cover.

The idea is that every minimum edge cover has the following structure: a matching as a skeleton, plus additional edges which cover only one additional vertex each, and are the cheapest edge out of that vertex. And the big graph containing $$G \cup G'$$ is exactly what we need to make its perfect matchings mimic that structure.

By the way, if $$G$$ is bipartite with bipartition $$(A,B)$$, then the graph created in steps 1-2 is also bipartite with bipartition $$(A \cup B', B \cup A')$$. So we get a bipartite minimum-weight matching problem to solve, which is nice.

• Is there a difference between this procedure and "start with a minimum weight full matching and, for each node not in the matching, add the cheapest edge connected to it"? Commented Jan 31, 2023 at 19:55
• Yes; the size of the matching you start with will end up being the number of components in your edge cover, so starting with a min-weight full matching can produce suboptimal results if the best edge cover has fewer components. For example, suppose we have a complete bipartite graph with vertices $v_1, \dots, v_n$ on one side and $w_1, \dots, w_n$ on the other, and we weight it so that edges out of $v_1$ or $w_1$ have weight $1$ while all other edges have weight $10$. Then a min-weight perfect matching has weight $2 + 10(n-2)$, but there is an edge cover with weight $2(n-1)$. Commented Jan 31, 2023 at 20:00
• "include the cheapest edge covering v in the edge cover" = "the cheapest edge in G that covers v"? Commented Jan 31, 2023 at 21:43
• Yes - where else? (But I've edited to clarify.) Commented Jan 31, 2023 at 21:45
• @ZiruiWang Unless $v$ is an isolated vertex in $G$, $v'$ has other neighbors in $G'$. Commented Jun 8, 2023 at 16:27