Path cover
Encyclopedia
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.
. 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.
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
.
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
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 setIndependent set (graph theory)
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
. 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
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...
follows as a corollary of this result.
Computational complexity
Given a digraph G, the minimum path cover problem consists of finding a path cover for G having the least number of paths.A minimum path cover consists of one path if and only if there is a Hamiltonian path
Hamiltonian path
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle in an undirected graph that visits each vertex exactly once and also returns to the starting vertex...
in G. The Hamiltonian path problem
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 or a Hamiltonian cycle exists in a given graph . Both problems are NP-complete...
is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, and hence the minimum path cover problem is NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
.