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
[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 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, see https://walkccc.me/CLRS/Chap26/Problems/26-2/.
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. Another application of minimum path covers problem is finding the minimum number of fleets and optimal dispatching of them to serve mobility demand in a city. [5]
See also
[edit]Notes
[edit]- ^ Diestel (2005), Section 2.5.
- ^ Franzblau & Raychaudhuri (2002).
- ^ Diestel (2005), Theorem 2.5.1.
- ^ Ntafos & Hakimi (1979)
- ^ Vazifeh, M. M.; Santi, P.; Resta, G.; Strogatz, S. H.; Ratti, C. (May 2018). "Addressing the minimum fleet problem in on-demand urban mobility". Nature. 557 (7706): 534–538. doi:10.1038/s41586-018-0095-1. ISSN 1476-4687.
References
[edit]- Bang-Jensen, Jørgen; Gutin, Gregory (2006), Digraphs: Theory, Algorithms and Applications (1st ed.), Springer.
- Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer.
- Franzblau, D. S.; Raychaudhuri, A. (2002), "Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow", ANZIAM Journal, 44 (2): 193–204, doi:10.1017/S1446181100013894.
- 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.