Partial and perfect path covers of cographs

A set ℘ of disjoint paths in a graph G is called a (complete) path cover of G if every vertex of G belongs to one of the paths in ℘. A path cover of any subgraph of G is called a partial path cover of G. For fixed k > 0, a k-blanket of graph G is a partial path cover ℘ of G, consisting of exactly k paths, that maximizes the size of the subgraph covered by ℘. A k-core of graph G is a partial path cover ℘ of G, consisting of exactly k paths, that minimizes the sum, over all vertices v of G, of the distance of v to its closest path in ℘. The problems of finding a k-blanket or a k-core (for fixed k) of an arbitrary graph G as well as the dual minimum-path-cover problem (find a path cover of minimum size) are all NP-hard. A linear-time algorithm is known (C.J. Chang and D. Kuo, SIAM J. Discrete Math. 9 (1996) 309-316) for the minimum-path-cover problem on cographs (graphs that can be constructed from a collection of isolated vertices by union and complement operations). However, prior to this paper, polynomial-time algorithms for the k-core problem were known only for trees - and even then for k = 1, 2 only (Becker and Perl, Discrete Appl. Math. 11 (1985) 103-113; Morgan and Slater, SIAM J. Appl. Math. 37 (1979) 539-560). In this paper, we introduce a variant of a minimum path cover, called a perfect path cover. We show that every cograph has a perfect path cover, and we exploit this to obtain an O(m + n log n)-time algorithm for finding, for any arbitrary k, a k-blanket or a k-core of a arbitrary cograph on n vertices and m edges. 1998 Published by Elsevier Science B.V. All rights reserved.