Kakimura, Naonori; Kawarabayashi, Ken-Ichi Packing directed circuits through prescribed vertices bounded fractionally. (English) Zbl 1256.05190 SIAM J. Discrete Math. 26, No. 3, 1121-1133 (2012). Summary: A seminal result of B. Reed et al. [Combinatorica 16, No. 4, 535–554 (1996; Zbl 0881.05050)] 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. G. Even et al. [Algorithmica 20, No. 2, 151–174 (1998; Zbl 0897.68078)] 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\). Cited in 6 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C20 Directed graphs (digraphs), tournaments 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) 05C38 Paths and cycles 05C85 Graph algorithms (graph-theoretic aspects) 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity 68W25 Approximation algorithms Keywords:disjoint circuits; feedback vertex sets; FPT approximability Citations:Zbl 0881.05050; Zbl 0897.68078 PDFBibTeX XMLCite \textit{N. Kakimura} and \textit{K.-I. Kawarabayashi}, SIAM J. Discrete Math. 26, No. 3, 1121--1133 (2012; Zbl 1256.05190) Full Text: DOI Link