2
$\begingroup$

I am looking for a reference for maximum cardinality weighted matching and the best running time algorithm for it.

Maximum Cardinality Weighted Matching: Given an undirected weighted graph $G(\mathcal{V},\mathcal{E})$ where $\mathcal{V}$ is set of vertices and $\mathcal{E}$ is the set of edges where each edge $(i,j) \in \mathcal{E}$ assigned a positive weight $w_{ij}$. Matching is the subset of edges such that no two edges share a vertex. The maximum cardinality weighted matching is the matching that maximizes the total weight of edges in the subset of matching that maximizes the total number of edges chosen in the matching

I searched but there is always maximum weighted matching which means the matching has maximum weight but may not has maximum cardinality all the time. I appreciate it if you can recommend a reference for the maximum cardinality weighted matching. I want the matching that maximizes the cardinality first then the weigt of the matching.

For example, 1 --- 2 --- 3 --- 4

The weight between 1 and 2 is 1. The weight between 2 and 3 is 10. The weight between 3 and 4 is 1.

The maximum cardinality weighted matching I want is 1--2 and 3--4.

The maximum weighted matching outputs 3--4

Improve this question
$\endgroup$
1
  • $\begingroup$ You can consider the problem as if it has two objectives maximizing the number of matched edges and the weight of edges but we give priority to the first objective. I want to find all the possible matching that maximize the number of edges. Then out of these possible set I choose the one that has the maximum weight. $\endgroup$
    – Salwa
    Commented Jan 19, 2021 at 7:33

1 Answer 1

Reset to default
1
$\begingroup$

If you take $S$ to be the sum of all the weights on all the edges in the graph and you add $S$ to all the weights in the graph, then a regular maximum weight matching will find you the matching you are looking for, since now with the large weights on all the edges, it will prefer a matching that uses the most number of edges first.

In your example of 1--2--3--4 with weights 1, 10, 1, here we have $S=12$, so add 12 to all the edges to have edge weights of 13, 22, 13 and now a regular max weight matching would prefer 13+13 over 22.

I'm not sure if it is easy to prove that $S$ is quite big enough, but it should be easy to prove that $mS$ is big enough to all to all edges (that is, sum of all edges times the number of edges).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks so much can you recommend a paper that uses this technique in a similar problem so I can write a concrete proof. $\endgroup$
    – Salwa
    Commented Jan 23, 2021 at 5:20
  • $\begingroup$ This is the same strategy used to show that TSP instances obeying triangle inequality are still NP-hard: given any TSP instance, can add a sufficiently large constant $K$ to all edges to make it obey triangle inequality, and we know any tour in the modified graph has $nK$ bloat in it. This can be found in the Cormen text, e.g. as exercise 35.2-2. Similarly, your G has a maximum matching size $M$ when ignoring edge weights and after adding sufficiently large K to everything, it favours number of edges and you can still remove bloat $MK$. $\endgroup$
    – JimN
    Commented Jan 24, 2021 at 11:59

Your Answer

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

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