A path cover of a directed 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.
a. 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'), where

b. and run a maximum-flow algorithm.)
c. Does your algorithm work for directed graphs that contain cycles? Explain.

Transcribed Image Text:

V = {xo, X1, ...„Nn} O {vo. V1, ... Vn} , E = {(xo, x) : iE V} E {(v yo) : i V} I {(x. y) : (1. j) I E},