I have a problem and want to know if there is any combinatorial optimization that is similar in nature to this problem or how to solve this special version of the max weight matching problem.

I have a general graph $G(\mathcal{V},\mathcal{E},\mathcal{W})$. I want to find a maximum weight matching of the graph $G$ that must cover a certain subset of vertices and has a specific size. For example, if I have a graph with eight vertices, I want to find a max weighted matching that must cover the subset of vertices $\mathcal{V}'=\{1,2,3\}$ and the size of the matching is $\lceil{|\mathcal{V}'|/2}\rceil$. So one more vertex needs to be chosen that maximizes the weighted matching. How to find the optimal solution in polynomial time if possible?


Maximum Weight Matching algorithms are incremental, so to achieve a maximum weight matching of a bounded size, just stop after so many iterations. To achieve the other constraint, For each terminal vertex in $\mathcal{V}'$, increase the weight of each incident edge by a huge constant amount $U$. Try to prove that this answers your question (note that edges incident to two terminals have to be increased twice to keep the total increase constant in all valid solutions).

Note. It might help in the proof to distinguish different cases according to the size of $\mathcal{V}'$ compared to $k$ (the size of the matching).

  • 1
    $\begingroup$ Thanks so much for your help. $\endgroup$ – Salwa Aug 14 '20 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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