Partial and perfect path covers of cographs

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.