Packing directed circuits through prescribed vertices bounded fractionally

A seminal result of Reed et al. [Combinatorica, 16 (1996), pp. 535-554] says that a directed graph has either κ vertex-disjoint directed circuits or a set of at most f(κ) vertices meeting all directed circuits. This paper aims at generalizing their result to packing directed circuits through a prescribed set S of vertices. Such a circuit is called an S-circuit. Even et al. [Algorithmica, 20 (1998), pp. 151-174] showed a fractional version of packing S-circuits. In this paper, we show that the fractionality can be bounded by at most one-fifth: Given an integer κ and a vertex subset S, whose size may not depend on κ, we prove that either G has a 1/5-integral packing of k disjoint S-circuits, i.e., each vertex appears in at most five of these S-circuits, or G has a vertex set X of order at most f(k) (for some function f of κ) such that G - X has no such circuit. We also give a fixed-parameter tractable approximation algorithm for finding a 1/5-integral packing of S-circuits. This algorithm finds a 1/5-integral packing of size approximately κ in polynomial time if it has a 1/5-integral packing of size k for a given directed graph and an integer κ.