Packing Directed Circuits through Prescribed Vertices Bounded Fractionally
Naonori Kakimura, Ken-ichi Kawarabayashi · SIAM Journal on Discrete Mathematics · 2012
A seminal result of Reed et al. [Combinatorica, 16 (1996), pp. 535--554] says that a directed graph has either $k$ vertex-disjoint directed circuits or a set of at most $f(k)$ 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 $k$ and a vertex subset $S$, whose size may not depend on $k$, 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 $k$) 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 $k$ in polynomial time if it has a $1/5$-integral packing of size $k$ for a given directed graph and an integer $k$.