Given a
directed graph ''G'' = (''V'', ''E''), a path cover is a set of
directed path
In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A directed path (sometimes c ...
s 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
In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician . ...
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
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a ...
is
NP-complete, and hence the minimum path cover problem is
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
. 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, see https://walkccc.me/CLRS/Chap26/Problems/26-2/.
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.
See also
*
Covering (disambiguation)#Mathematics
Notes
References
*.
*.
*.
*.
{{DEFAULTSORT:Path Cover
Graph theory objects