Finding a minimum path cover of a distance-hereditary graph in polynomial time ?
A path cover  of a graph G=(V,E) G = ( V , E ) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V V of G G . The path cover problem  is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O(|V|9 | V | 9 ) time, to solve the path cover problem on distance-hereditary graphs.
path cover distance-hereditary graphs hamiltonian path graph algorithms