# Combinatorial Problem similar in nature to a special version of max weighted matching problem

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?

## 1 Answer

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

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