## General Weighted Perfect Matching

**Moderator:** Board moderators

### General Weighted Perfect Matching

Hi, i wish to know how to solve the problem of finding a maximal matching with minimum weight in general graphs, (not just bipartite graphs), from comments about problem 10911, it seems to be an algorithm in O(2^n * n^2), wich uses DP, i am particularly interested in this solution, because i have not been able to identify the subproblems or the way in how the table is structured and filled, any other information is appreciated too, thanks in advance

Well, if it's in O(2^n * n^2) time, then here it goes:

Well, first you are given the vertices {1,2,3,4,5,6,7...,n}

You would like to pick some edge from the set, say 4 and 6 (can be any 2, in general, you can all possible pairs, which where n^2 come from)

So, now, just say in one particular case we pick (4,6), so now in this potential solution we have Cost(4,6) included in our score (that we try to maximize), and the rest of the set {1,2,3,5,7,...,n} to pick, which is our subproblem. To figure out the best set of edges you can pick from that subproblem, you recursively call the instance. Now, there are 2^n instances, thus there will be at most 2^n recursive calls, and each of them will try to pick one edge (and there are in general n^2 edges to choose from), which makes the algorithm O(2^n * n^ 2).

It is dynamic programmable because the size of your set (problem instance) sets the stage (or, optimal sub-structure) of the recursion.

Hope it helps