Hi, guy!
There is a problem which has statement :
Given n people and m job, c[i][j] represent the cost if people i match with job j. Find a max matching with minimum cost.
This problem can be solve with Hungary algorithm for max matching and minimum cost in bipartite graph. But some time, I see some problem which similar the statement below :
Given n people, c[i][j] represent the cost if people i match with people j. Find a matching and with maximum cost.
The bipartite property is not hold in this problem, but I think there's some way to modify it to bipartite graph and solve it by Hungary algorithm, but this problem also has tag "maxflow". So, I wonder how to solve this with maxflow-mincost algorithm because it must be hold that if the people i match with people j, then people i and j mustn't match with any another people.
(Sorry because my English)
basically the trick is to put $$$n$$$ people on both sides of the bipartite graph, and run edges with cost $$$c_{i,j}$$$ from the left side to the right side. the idea is that if you have some min-cost matching with the edge $$$(a, b)$$$, then in this modified graph, you will take the edge $$$a \rightarrow b$$$ for cost $$$c_{a,b}$$$ and the edge $$$b \rightarrow a$$$ for the cost $$$c_{b, a} = c_{a, b}$$$. in the end, your matching will have double the cost that it should have, because you take each edge twice. note that you have to be very careful about trying to recover your answer, as you might not do the exact same matching two times (you might do it once, and then do a second, equivalent cost matching in the reverse direction).
Does this algorithm always work? Perhaps I'm not fully understanding the details, but if we simply run a weighted matching algorithm on the bipartite graph formed from doubling the vertices, we run into cases like this:
Corresponds to the following graph: https://ibb.co/JyMxcnv
And the following bipartite graph: https://ibb.co/k3dSRKk
Have to use external links since insert image function seems to be broken.
In such a case, the maximum cost matching you can get doesn't involve doubling any edge we take, but instead taking the edge set (1, 2), (2, 3), (3, 1) for a total cost of 10, or 5 when halved, but the answer is 4 (take the edge (1, 2) or (2, 3)).
Modifying the standard matching algorithm to circumvent this doesn't seem trivial. For example, one could always force the edge (b, a) into the matching when taking (a, b), but part of the maximal matching algorithm involves adjusting the matching via augmenting paths, which I don't think would work if we're forced to keep certain pairs of edges in the matching. Perhaps Edmond's Blossom algorithm could be used instead.
edit: yeah i think you're right, my bad. i thought you could get around it by adding an extra node with 0 weight edges to all nodes in the case that $$$n$$$ is odd, but replicating your graph on 6 nodes breaks it. thanks a ton!
it seems that there is a blossom algorithm variant that will min-cost perfect matching on general graphs (not just complete graphs) here, which will work for this problem.