<p>If all edge weights are non-negative, then the minimum weight set of edges that covers all the nodes automatically has the property that it has no three-edge paths, because the middle edge of any such path would be redundant. If we assign each vertex to an edge that covers it, some edges will cover both of their endpoints (forming a matching $M$) and others will cover only one of their endpoints (and must be the minimum weight edge adjacent to the covered endpoint). If we let $c_v$ be the cost of the minimum weight edge incident to vertex $v$, and $w_e$ be the weight of $e$, then the cost of a solution is $\sum_{v\in G} c_v + \sum_{(u,v)\in M} (w_{(u,v)}-c_u-c_v)$. The first sum doesn't depend on the choice of the cover, so the problem becomes one of finding a matching that maximizes the total weight, for edge weights $c_u+c_v-w_{(u,v)}$. If you really want this to be a minimum weight perfect matching problem, then instead use weights $w_{(u,v)}-c_u-c_v$ and add enough dummy edges with weight zero to guarantee that any matching with the real edges can be extended to a perfect matching by adding dummy edges.</p>

<p>If the input graph can have negative edge weights, then the three-edge-path constraint becomes meaningful. In this case it's not obvious to me that there is a polynomial time solution.</p>

CC BY-SA 3.0
2016-10-19T15:08:02.450Z
You've shown that the minimum weight covering problem can be reduced to the maximum weight matching problem.  But, can it be reduced to a 'bipartie' maximum matching problem?
Nimrand
CC BY-SA 3.0
2016-10-19T18:52:38.793Z
It's a maximum weight matching problem on the original graph, which was assumed in the stated problem to be bipartite.
David Eppstein
CC BY-SA 3.0
2016-10-19T23:49:10.497Z
Ah, I missed that the original graph was also bipartie.  Does the same formulation work for converting a general Minimum Weighted Covering problem to a general Maximum Matching problem?  I know from Marco[90] they can be converted, but this formulation seems more it would be more efficient in some cases.
Nimrand
CC BY-SA 3.0
2012-12-31T21:43:45.537Z
2012-12-31T21:43:45.537Z
David Eppstein
<p>The solution can be found in:</p>
<p>Editor: Mikhail J. Atallah
Handbook on Algorithms and Theory of Computation
1998, CRC Press, ISBN: 0849326494</p>

CC BY-SA 4.0
2022-07-29T19:59:00.263Z
2022-07-29T19:59:00.263Z
Vahid Rafael
<p>I have a set of edges [m,n] of a bipartie graph U, V with a cost assigned to each edge and I need to find the minimum cost edge-cover covering all nodes in U, V. There is one additional constraint is that I should not have a length 3 path ( meaning if m in [m,n] is included in other edges then n should not happen on other edges than [m,n] )</p>

<p>I have read that this problem can be reduced to a minimum cost weighted bipartie perfect matching, but I could not find the way to do that.</p>

<p>The relation is not straightforward to me since a node m can be connected to different nodes in the right hand partie and vice versa.</p>

CC BY-SA 3.0
2012-12-10T14:06:41.393Z
It should be MAXIMUM matching； a minimum matching can be nothing than an empty set.  Hint: An edge-cover is a superset of the max matching.  Your additional constraint is redundant, and can be derived from the "minimum cost".
Yixin Cao
CC BY-SA 3.0
2012-12-10T14:37:06.323Z
I meant minimum cost of a weighted bipartie matching, if you are talking about the title. If so I can reformulate it this way
Sadache
CC BY-SA 3.0
2012-12-10T18:19:54.653Z
have you ever checked the definition of "matching"?
Yixin Cao
CC BY-SA 3.0
2012-12-10T19:38:35.670Z
I did, how does that help in answering my question?
Sadache
CC BY-SA 3.0
2012-12-10T20:09:48.707Z
Sadache, the confusion is that if all weights are positive, then the minimum cost matching is just an empty set. what makes more sense is consider the minimum cost matching of cardinality $k$. then a sensible choice for $k$ is the maximum cardinality of any matching in the graph.
Sasho Nikolov
CC BY-SA 3.0
2012-12-10T20:41:09.233Z
yeah sure, you are right. What I need to reduce a minimum cost edge-cover to a perfect matching of a bipartie graph with minimum cost.
Sadache
CC BY-SA 3.0
2012-12-10T22:20:50.443Z
done, thank for helping me clarifying my question.
Sadache
CC BY-SA 3.0
2012-12-11T01:53:28.970Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.
Kaveh
CC BY-SA 3.0
2012-12-31T21:45:22.040Z
I think the problem of finding a minimum cost edge cover, without the path length constraint, would not be research level. But with the constraint (and with negative edges) it seems nontrivial enough to me, so I am upvoting this.
David Eppstein
<graph-algorithms><matching>
Reducing a minimum cost edge-cover problem to minimum cost weighted bipartie perfect matching
Sadache
# Reducing a minimum cost edge-cover problem to minimum cost weighted bipartie perfect matching

(Asked by: username_0 on 2012-12-10)

I have a set of edges [m,n] of a bipartie graph U, V with a cost assigned to each edge and I need to find the minimum cost edge-cover covering all nodes in U, V. There is one additional constraint is that I should not have a length 3 path ( meaning if m in [m,n] is included in other edges then n should not happen on other edges than [m,n] )

I have read that this problem can be reduced to a minimum cost weighted bipartie perfect matching, but I could not find the way to do that.

The relation is not straightforward to me since a node m can be connected to different nodes in the right hand partie and vice versa.

**Tags:** graph-algorithms, matching

> **Comments:**
> **username_1**: It should be MAXIMUM matching； a minimum matching can be nothing than an empty set.  Hint: An edge-cover is a superset of the max matching.  Your additional constraint is redundant, and can be derived from the "minimum cost".  
> **username_0**: I meant minimum cost of a weighted bipartie matching, if you are talking about the title. If so I can reformulate it this way  
> **username_1**: have you ever checked the definition of "matching"?  
> **username_0**: I did, how does that help in answering my question?  
> **username_2**: username_0, the confusion is that if all weights are positive, then the minimum cost matching is just an empty set. what makes more sense is consider the minimum cost matching of cardinality $k$. then a sensible choice for $k$ is the maximum cardinality of any matching in the graph.  
> **username_0**: yeah sure, you are right. What I need to reduce a minimum cost edge-cover to a perfect matching of a bipartie graph with minimum cost.  
> **username_0**: done, thank for helping me clarifying my question.  
> **username_3**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.  
> **username_4**: I think the problem of finding a minimum cost edge cover, without the path length constraint, would not be research level. But with the constraint (and with negative edges) it seems nontrivial enough to me, so I am upvoting this.  

---

## 2 answers

### Answer by username_4 on 2012-12-31. Score: 7

If all edge weights are non-negative, then the minimum weight set of edges that covers all the nodes automatically has the property that it has no three-edge paths, because the middle edge of any such path would be redundant. If we assign each vertex to an edge that covers it, some edges will cover both of their endpoints (forming a matching $M$) and others will cover only one of their endpoints (and must be the minimum weight edge adjacent to the covered endpoint). If we let $c\_v$ be the cost of the minimum weight edge incident to vertex $v$, and $w\_e$ be the weight of $e$, then the cost of a solution is $\sum\_{v\in G} c\_v + \sum\_{(u,v)\in M} (w\_{(u,v)}-c\_u-c\_v)$. The first sum doesn't depend on the choice of the cover, so the problem becomes one of finding a matching that maximizes the total weight, for edge weights $c\_u+c\_v-w\_{(u,v)}$. If you really want this to be a minimum weight perfect matching problem, then instead use weights $w\_{(u,v)}-c\_u-c\_v$ and add enough dummy edges with weight zero to guarantee that any matching with the real edges can be extended to a perfect matching by adding dummy edges.

If the input graph can have negative edge weights, then the three-edge-path constraint becomes meaningful. In this case it's not obvious to me that there is a polynomial time solution.

> **Comments:**
> **username_5**: You've shown that the minimum weight covering problem can be reduced to the maximum weight matching problem.  But, can it be reduced to a 'bipartie' maximum matching problem?  
> **username_4**: It's a maximum weight matching problem on the original graph, which was assumed in the stated problem to be bipartite.  
> **username_5**: Ah, I missed that the original graph was also bipartie.  Does the same formulation work for converting a general Minimum Weighted Covering problem to a general Maximum Matching problem?  I know from Marco[90] they can be converted, but this formulation seems more it would be more efficient in some cases.  

---

### Answer by username_6 on 2022-07-29. Score: 0

The solution can be found in:

Editor: Mikhail J. Atallah
Handbook on Algorithms and Theory of Computation
1998, CRC Press, ISBN: 0849326494


---

