Disjoint cycles intersecting a set of vertices

AbstractA classic theorem of Erdős and Pósa states that there exists a constant c such that for all positive integers k and graphs G, either G contains k vertex disjoint cycles, or there exists a subset of at most cklogk vertices intersecting every cycle of G. We consider the following generalization of the problem: fix a subset S of vertices of G. An S-cycle is a cycle containing at least one vertex of S. We show that again there exists a constant c′ such that G either contains k disjoint S-cycles, or there exists a set of at most c′klogk vertices intersecting every S-cycle. The proof yields an algorithm for finding either the disjoint S-cycles or the set of vertices intersecting every S-cycle. An immediate consequence is an O(logn)-approximation algorithm for finding disjoint S-cycles