how to reduce Maximum cardinality bipartite matching to minimum path cover?

Question

I have read these two questions : link1 link2

and also this wikipedia

but i can't understand how solving maximum matching problem can be used to solve minimum path cover. I know the solution is n-m where n is the number of vertices in G and m is the maximum matching but i can't find the reason

Answer 1

Here is an intuitive explanation of this fact(it is not a rigorous proof): Let's take a look at each path in a path cover. Every vertex, except the first one in a path, has a unique predecessor. Moreover, each vertex has exactly one successor(except the last on in each path). That's why we can say that each vertex is matched to its predecessor. If a vertex is not matched to anything, it is the first vertex in some path. That's why the number of paths is equal to the number of unmatched vertices(each path has exactly one first vertex). The number of unmatched vertices is obviously equal to the total number of vertices minus the number of matched vertices. That's how we get n - m formula. It is not possible to get less paths then the size of a maximum matching(otherwise n - m1 < n - m => m1 > m => m is not maximum). At the same time, we can construct a solution with n - m paths explicitly.

Answer 2

• You have n nodes on the left & m nodes on the right.
• After matching you calculate maxFlow f - maximum number of matches.
• f nodes on the left & f nodes on the right are in min edge cover already.
• On the left there're n-f nodes that are not in matching, on the right there're m-f such nodes.
• These nodes are not in min cover yet, because maximum matching didn't include them.
• Each of these nodes can be connected to min edge cover. So it adds (n-f)+(m-f) edges.
• So in total min cover is f+(n-f)+(m-f)=n+m-f

Here's a min edge cover problem: https://code.google.com/codejam/contest/11254486/dashboard#s=p2&a=2