Given a $G(A,B,E)$ bipartite graph and a $w: E \to R$ weight function.
Problem 1: We are looking for a $M$ matching where the sum of the weights of edges in the M matching is maximal.
This problem can be solved using the solution of another problem:
Problem 2: Looking for a maximal $M$ perfect Matching.
To use this solution, you have to make same changes to your original graph in the first problem:
0: remove negative value edges (you won't need that anyway, doesn't add any value to the total sum of the matching)
1: if $|A|$ is now equal $|B|$ add "virtual" nodes to the smaller group
2: Add virtual edges to each non-neighbouring $A$-$B$ nodes, with $0$ weight value.
Run the second solution/algorithm (Hungarian method could be used) with the input of the generated graph.
Take the output of the second algorithm, remove each virtual nodes and edges. The result is a solution for the original problem.
My question is, how to prove the correctness of this solution for the original problem?
I know some points, but I am not completely sure about the total correctness of my proof. Maybe I miss some points.
1: You can be sure that you remove only 0 value edges and virtual nodes when you remove virtual "things" from your solution. S the result's total edge-weight sum won't decrease.
2: Let's say there is an even bigger Matching for the first problem, that was not found by the second algorithm
3: Proove that this can't be the case, since if there is a Matching with larger total-weight, then the second algorithm should have found that. Indirect proof.
Could you please help me to turn this into a more formal way and make sure that I have everything included in my proof?
Thank you.
Let's assume using this solution you got a n total weight matching found by the 2. algorithm.
When removing the virtual things from the graph you are still going to have an n sized total weight matching solution for the original problem (only virtual edges and nodes are removed, so this way the size won't decrease. You should only remove edges with weight > 0 to decrease the total weight of the matching.)
To disprove the correctness of the solution you must show a bigger total weight matching for the original problem. Let's say you have a n+1 total weight matching for the original problem.
We are going to see that this can't be. If you had an n+1 sized total weight matching in the original graph for the original problem, you should get an n+1 sized solution for the transformed graph's maximal weight perfect matching.
We added only edges with 0 value, so these only will be in the output matching if no other edges could be used with higher weight value. This way we should get the n+1 total weight solution if one existed.
Both directions are proved this way.