4
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. ) $\endgroup$ Commented Feb 1, 2023 at 0:21
  • $\begingroup$ @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) $\endgroup$
    – Xilef11
    Commented Feb 1, 2023 at 13:15
  • $\begingroup$ @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. $\endgroup$ Commented Feb 1, 2023 at 14:54

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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"? $\endgroup$
    – Xilef11
    Commented Jan 31, 2023 at 19:55
  • $\begingroup$ 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)$. $\endgroup$ Commented Jan 31, 2023 at 20:00
  • $\begingroup$ "include the cheapest edge covering v in the edge cover" = "the cheapest edge in G that covers v"? $\endgroup$
    – Xilef11
    Commented Jan 31, 2023 at 21:43
  • 1
    $\begingroup$ Yes - where else? (But I've edited to clarify.) $\endgroup$ Commented Jan 31, 2023 at 21:45
  • 1
    $\begingroup$ @ZiruiWang Unless $v$ is an isolated vertex in $G$, $v'$ has other neighbors in $G'$. $\endgroup$ Commented Jun 8, 2023 at 16:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .