A set P of disjoint paths in a graph G is called a (complete) path cauer of
G if every vertex of G belongs to one of the paths in P. A path cover of a
ny subgraph of G is called a par tial path cover of G. For fixed k>0, a k-b
lanket of graph G is a partial path cover P of G, consisting of exactly k p
aths, that maximizes the size of the subgraph covered by P. A k-core of gra
ph G is a partial path cover P of G, consisting of exactly k paths, that mi
nimizes the sum, over all vertices v of G, of the distance of v to its clos
est path in P. 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 (f
ind 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) f
or the minimum-path-cover problem on cographs (graphs that can be construct
ed from a collection of isolated vertices by union and complement operation
s). 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 a
nd Perl, Discrete Appl. Math. Il (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 cograp
h has a perfect path cover, and we exploit this to obtain an O(Pn + 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 Elsevie
r Science B.V. All rights reserved.