Minimum path cover in DAG

Question

I want to know if there exists an efficient algorithm for computing the minimum path-cover in a Directed Acyclic Graph. Please don't confuse the minimum "path-cover" with "vertex-disjoint path-cover". For the latter, I know an efficient algorithm using Maximum matching of the corresponding Bipartite graph. But that applies only for the vertex-disjoint case. Can the same algorithm be relaxed to obtain the answer for the path cover when each vertex can be visited multiple times?

Answer 1

Yes, the same algorithm could be relaxed as you wish. Just compute transitive closure of the original graph.

You can find an explanation of the complete algorithm in Wikipedia article "Dilworth's theorem", in section "Proof via König's theorem".