Packing directed cycles efficiently

Let G be a simple digraph. The dicycle packing number of G  , denoted νc(G)ν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 ww. A function ψψ from the set CC of directed cycles in G   to R+R+ is a fractional dicycle packing of G   if ∑e∈C∈Cψ(C)⩽w(e)∑e∈C∈Cψ(C)⩽w(e) for each e∈E(G)e∈E(G). The fractional dicycle packing number  , denoted νc*(G,w), is the maximum value of ∑C∈Cψ(C)∑C∈Cψ(C) taken over all fractional dicycle packings ψψ. In case w≡1w≡1 we denote the latter parameter by νc*(G).Our main result is that νc*(G)-νc(G)=o(n2) where n=|V(G)|n=|V(G)|. Our proof is algorithmic and generates a set of arc-disjoint directed cycles whose size is at least νc(G)-o(n2)νc(G)-o(n2) in randomized polynomial time. Since computing νc(G)νc(G) is an NP-Hard problem, and since almost all digraphs have νc(G)=Θ(n2)νc(G)=Θ(n2) our result is a FPTAS for computing νc(G)νc(G) for almost all digraphs.The result uses as its main lemma a much more general result. Let FF be any fixed family of oriented graphs. For an oriented graph G  , let νF(G)νF(G) denote the maximum number of arc-disjoint copies of elements of FF that can be found in G  , and let νF*(G) denote the fractional relaxation. Then, νF*(G)-νF(G)=o(n2). This lemma uses the recently discovered directed regularity lemma as its main tool.It is well known that νc*(G,w) can be computed in polynomial time by considering the dual problem. We present a polynomial algorithm that finds an optimal fractional dicycle packing. Our algorithm consists of a solution to a simple linear program and some minor modifications, and avoids using the ellipsoid method. In fact, the algorithm shows that a maximum fractional dicycle packing with at most O(n2)O(n2) dicycles receiving nonzero weight can be found in polynomial time.