Solving the path cover problem on circular-arc graphs by using an approximation algorithm ?
A path cover  of a graph G=(V,E) G = ( V , E ) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem  is to find a path cover of minimum cardinality. This paper presents a simple O(n) O ( n ) -time approximation algorithm for the path cover problem on circular-arc graphs given a set of n  arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) O ( n ) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs.
path cover circular-arc graphs hamiltonian cycle hamiltonian path graph algorithms interval graphs