An optimal parallel solution for the path cover problem on P4-sparse graphs

Nakano et al. [A time-optimal solution for the path cover problem on cographs, Theoret. Comput. Science 290 (2003) 1541–1556] presented a time- and work-optimal algorithm for finding the smallest number of vertex-disjoint paths that cover the vertices of a cograph and left open the problem of applying their technique into other classes of graphs. Motivated by this issue we generalize their technique and apply it to the class of P4-sparse graphs, which forms a proper superclass of cographs. We show that the path cover problem on P4-sparse graphs can also be optimally solved. More precisely, given a P4-sparse graph G on n vertices and its modular decomposition tree, we describe an optimal parallel algorithm which returns a minimum path cover of G in O(logn) time using O(n/logn) processors on the EREW PRAM model. Our results generalize previous results and extend the family of perfect graphs admitting optimal solutions for the path cover problem.