Let G be a simple digraph. The dicycle packing number of G, denoted V_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 if) from the set C of directed cycles in G to R+ is a fractional dicycle packing of G if Σ_(e∈C ∈C) ψ(C) ≤ w(e) for each e ∈ E(G). The fractional dicycle packing number, denoted V_c~*(G,w), is the maximum value of Σ_(C ∈C) ψ(C) taken over all fractional dicycle packings ψ. In case w ≡ 1 we denote the latter parameter by v_c~*(G). Our main result is that v_c~*(G) - v_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 v_c(G) - o(n~2) in randomized polynomial time. Since computing v_c(G) is an NP-Hard problem, and since almost all digraphs have v_c(G) = Θ(n~2) our result is a FPTAS for computing v_c(G) for almost all digraphs. The latter result uses as its main lemma a much more general result. Let F be any fixed family of oriented graphs. For an oriented graph G, let v_F(G) denote the maximum number of arc-disjoint copies of elements of F that can be found in G, and let v_F~*(G) denote the fractional relaxation. Then, V_F~*(G) - v_F(G) = o(n~2). This lemma uses the recently discovered directed regularity lemma as its main tool. It is well known that v_c~*(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 v_2~*(G,w) can be generated in polynomial time. We prove that a maximum fractional dicycle packing yielding v_c~*(G, w) with at most O(n~2) dicycles receiving nonzero weight can be found in polynomial time.
展开▼
