A path cover is a collection of paths covering certain features of a digraph, such as its vertices, edges, selected pairs of vertices, etc. Such covers arise in program testing strategies where programs are modeled by digraphs. The problems considered vary according to the graphical elements to be covered (vertices, edges, vertex subsets) and the type of digraph (acyclic, structured (acyclic only]), trees). Most of the problems considered are shown to be NP-complete or NP-hard. A very general path cover problem is shown to be polynomial, provided a partial order on the elements to be covered can be defined in polynomial time. A path covering problem is conjectured to be NP-complete if no partial order on the elements to be covered can be defined in polynomial time. A classical result of Dilworth relating the size of a minimum path cover and the maximum number of incomparable vertices is generalized for several path cover problems.

The paper presents interesting results in a clear and self-contained manner. Applicability to program testing is limited by the acyclic restriction on structured digraphs.