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).^[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

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

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

Applications

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

• Covering (graph theory)

Notes

1. ^ Diestel (2005), Section 2.5.
2. ^ Franzblau & Raychaudhuri (2002).
3. ^ Diestel (2005), Theorem 2.5.1.
4. ^ Ntafos & Hakimi (1979)

References

• Bang-Jensen, Jørgen; Gutin, Gregory (2006), Digraphs: Theory, Algorithms and Applications (1st ed.), Springer, http://www.cs.rhul.ac.uk/books/dbook/ .
• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ .
• Franzblau, D. S.; Raychaudhuri, A. (2002), "Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow", ANZIAM Journal 44 (02): 193–204, doi:10.1017/S1446181100013894, http://www.austms.org.au/Publ/Jamsb/V44P2/1761.html .
• Ntafos, S. C.; Hakimi, S. Louis. (1979), "On path cover problems in digraphs and applications to program testing", IEEE Transactions on Software Engineering 5 (5): 520–529, doi:10.1109/TSE.1979.234213, http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1702662 .