Bipartite graph “matching” with multiple edges per node

bipartite-graphsgraph theorymatching-theoryterminology

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?

Best Answer

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.

Related Question