Animation scientifique

The Path Cover problem is a fundamental graph algorithmic problem that asks whether the vertices of a given graph $G$ can be covered using a collection of $k$ paths of $G$.  Path Cover  contains the celebrated Hamiltonian Path problem as a special case (when $k=1$). Indeed, when a graph is not Hamiltonian, it is quite fair to ask what is the minimum number of paths required to cover all of its vertices. While it is usual to ask that all the paths in the covering are vertex-disjoint, we here consider the parameterized complexity of the unrestricted version (where the paths are not necessarily disjoint), namely with regard to the Cluster Vertex Deletion number and Feedback Edge Number of the input graph.