On the computational complexity of path cover problems

摘要

In this paper the complexity of a number of path cover problems in acyclic digraphs, acyclic structured digraphs, and rooted trees is considered. The problems deal with finding path covers of a certain size for (a) some elements of the digraph (e.g., required pairs, vertex subsets) or (b) the vertices of the digraph when restrictions are placed on the members of the path cover (e.g., impossible pairs, length-constrained covers). An attempt is made to characterize the complexity of path cover problems in general and a connection between the complexity of a path cover problem and the existence of a reachability relation on the elements that are to be covered in the digraph is pointed out.