Min weighted edge cover - is the greedy algorithm sub-optimal? The post here: Solving the min edge cover using the maximum matching algorithm provides a way to obtain the min edge cover from a maximum matching by greedily adding edges on top of the maximum matching until all vertices are covered. Now, thinking about the min-weighted edge cover problem, it would seem this approach can be extended. First, find the minimum weighted matching with maximum edges, and then add edges of the smallest weight greedily, smallest weight ones first.
However, reading section 19.3 of the book &quot;Combinatorial optimization: polyhedra and efficiency&quot; by Schrijver, a more complicated algorithm is presented. This makes it seem like my approach above is sub-optimal. Is it possible to find a counter-example, preferably on a bi-partite graph where my greedy algorithm would fail to provide an optimal solution? I haven't been able to find one with some toy graphs.
Here is a counterexample to your proposed algorithm:

The optimal solution consists of 3 edges and costs 3+1+1=5, but the min-cost maximum-cardinality matching, which consists of 2 edges and costs 3+3=6, will be chosen by the first step of your algorithm and immediately returned, as it is already a solution. (The only other maximum-cardinality matching costs 1+6=7.)