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 path cover for "G" having the fewest paths. A minimum path cover consists of one path if and only if there is a Hamiltonian path in "G". The Hamiltonian path problem is NP-complete, and hence the minimum  path cover problem is NP-hard. However, if the graph is acyclic, the problem is in complexity class P and can therefore be solved in polynomial time by transforming it into a matching problem. Applications. The applications of minimum path covers include software testing. For example, if the graph "G" represents all possible execution sequences of a computer program, then a path cover is a set of test runs that covers each program statement at least once.