2
$\begingroup$

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 "Combinatorial optimization: polyhedra and efficiency" 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.

Improve this question
$\endgroup$
5
  • $\begingroup$ "First, find the minimum weighted edge cover" -- that is the top-level problem you're trying to solve, so I think you meant something else here. But it's not clear what, since if you meant "the minimum-weight matching", that would be the empty matching (assuming positive edge weights), while "the maximum-weight matching" will certainly give you suboptimal solutions in certain cases (consider, e.g., a square in which 2 opposite edges have high weight and the other two edges have low weight). $\endgroup$
    – j_random_hacker
    Nov 27, 2020 at 20:02
  • $\begingroup$ @j_random_hacker - Good catch. I meant the matching of maximal size that has the minimum weight. I suppose this isn't easy to find? $\endgroup$
    – Rohit Pandey
    Nov 27, 2020 at 20:12
  • $\begingroup$ I don't know the answer to that, but if negative weights can be used in a max-weight matching algorithm, then this could be used to find a matching of maximal size having minimum weight: First negate all edge weights, then add in all missing edges with a tiny negative weight. Now find the max-weight matching, and then discard all edges in it that you just added. $\endgroup$
    – j_random_hacker
    Nov 27, 2020 at 20:47
  • $\begingroup$ Can you clarify "missing edges"? In section 17.2 of Schrijver, when describing the Hungarian method, he requires a weight function $w: E \to Q$ so I suppose negative weights are possible. $\endgroup$
    – Rohit Pandey
    Nov 27, 2020 at 20:56
  • 1
    $\begingroup$ I just meant any edges not already present in the input graph. That's good news about the Hungarian method, but as you can see I found a counterexample anyway... $\endgroup$
    – j_random_hacker
    Nov 27, 2020 at 21:04

1 Answer 1

Reset to default
1
$\begingroup$

Here is a counterexample to your proposed algorithm:

enter image description here

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.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.