×

Packing directed circuits through prescribed vertices bounded fractionally. (English) Zbl 1256.05190

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\).

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
PDFBibTeX XMLCite
Full Text: DOI Link