Packing Directed Cycles Efficiently

Abstract Let G be a simple digraph. The dicycle packing number of G, denoted ν c ( G ), is the maximum size of a set of arc-disjoint directed cycles in G. Let G be a digraph with a nonnegative arc-weight function w. A function ψ from the set \({\cal C}\) of directed cycles in G to R + is a fractional dicycle packing of G if \(\sum_{e \in C \in {\cal C}} {\psi(C)} \leq w(e)\) for each e ∈ E ( G ). The fractional dicycle packing number, denoted ν \(_{c}^{\rm *}\) ( G, w ), is the maximum value of \(\sum_{C \in {\cal C}} \psi(C)\) taken over all fractional dicycle packings ψ. In case w ≡ 1 we denote the latter parameter by ν \(_{c}^{\rm *}\) ( G ). Our main result is that ν \(_{c}^{\rm *}\) ( G ) – ν c ( G )= o ( n 2 ) where n =| V ( G )|. Our proof is algorithmic and generates a set of arc-disjoint directed cycles whose size is at least ν c ( G )- o ( n 2 ) in randomized polynomial time. Since computing ν c ( G ) is an NP-Hard problem, and since almost all digraphs have ν c ( G )=Θ( n 2 ) our result is a FPTAS for computing ν c ( G ) for almost all digraphs. The latter result uses as its main lemma a much more general result. Let \({\cal F}\) be any fixed family of oriented graphs. For an oriented graph G, let \(\nu_{\cal F}(G)\) denote the maximum number of arc-disjoint copies of elements of \({\cal F}\) that can be found in G, and let \(\nu_{\cal F}^*(G)\) denote the fractional relaxation. Then, \(\nu_{\cal F}^*(G) - \nu_{\cal F}(G)=o(n^2)\). This lemma uses the recently discovered directed regularity lemma as its main tool. It is well known that ν \(_{c}^{\rm *}\) ( G, w ) can be computed in polynomial time by considering the dual problem. However, it was an open problem whether an optimal fractional dicycle packing ψyielding ν \(_{c}^{\rm *}\) ( G, w ) can be generated in polynomial time. We prove that a maximum fractional dicycle packing yielding ν \(_{c}^{\rm *}\) ( G, w ) with at most O ( n 2 ) dicycles receiving nonzero weight can be found in polynomial time.

Authors

• Zeev Nutov
• Raphael Yuster

Keywords

No keywords are indexed for this paper.