Graph Theory

A path cover of a directed acyclic graph G(V, E) is a set P of vertex-disjoint paths such that every vertex in V is included in exactly one path in P. Paths may start and end anywhere, and they may be of any length, including 0. A minimum path cover of G is a path cover containing the fewest possible paths. Give an efficient algorithm to find a minimum path cover of a directed acyclic graph G(V, E).

Hint: Assuming that V ={1,2,...,n} construct the graph G =(V,E),whereV ={x0,x1,x2,...,xn} {y0 , y1 , y2 , . . . , yn }, E = {(x0 , xi ) : i V } {(yi , y0 ) : i V } {(xi , yj ) : (i, j ) E } and run a maximum-flow algorithm.)