Path cover

Given a directed graph G = (V, E), a path cover is a set of directed paths such that every vertex v ∈ V belongs to at least one path. Note that a path cover may include paths of length 0 (a single vertex).
A path cover may also refer to a vertex-disjoint path cover, i.e., a set of paths such that every vertex v ∈ V belongs to exactly one path.
Properties
A theorem by Gallai and Milgram shows that the number of paths in a smallest path cover cannot be larger than the number of vertices in the largest independent set. In particular, for any graph G, there is a path cover P and an independent set I such that I contains exactly one vertex from each path in P. Dilworth's theorem follows as a corollary of this result.
Computational complexity
Given a directed graph G, the minimum path cover problem consists of finding a...