Path cover

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Given a directed graph G = (VE), 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).[1]

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.[2]

Properties[edit]

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.[3] 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[edit]

Given a directed graph 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 in G. The Hamiltonian path problem is NP-complete, and hence the minimum path cover problem is NP-hard.

Applications[edit]

The applications of minimum path covers include software testing.[4] 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[edit]

Notes[edit]

References[edit]