# graphs – Min path cover problem in Cormen et.al. question about notation

In the book on algorithms by Cormen et.al, the problem 26-2 describes how to obtain a min-path cover for a DAG via max-flow. I have a question about the notation. First, let me quote the problem here:

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:

$$V’ = {x_0,x_1,dots x_n} cup {y_0, y_1, dots y_n}$$
$$E’={(x_0,x_i):i in V} cup {(y_i,y_0) : i in V} cup {(x_i,y_i):(i,j) in E}$$
and run a maximum-flow algorithm.)

What are the $$x_i$$ and $$y_i$$ here? Am I missing something obvious?

Posted on Categories Articles