Before revision: A minimum path cover (MPC) of a directed acyclic graph (DAG) G = (V, E) is a minimum-size set of paths that together cover all the vertices of the DAG. The size k of a MPC is also called the width of G. Computing a MPC is a basic problem, dating back to Dilworth's and Fulkerson's results in the 1950s, and is solvable in quadratic time in the worst case.
After revision: A minimum path cover (MPC) of a directed acyclic graph (DAG) G = (V, E) equals the largest number of pairwise non-reachable vertices. Computing the width dates back to Dilworth's and Fulkerson's results in the 1950s, and is solvable in quadratic time in the worst case.