Packing directed cycles efficiently

Zeev Nutov, Raphael Yuster

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


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 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 ν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 νc* (G). Our main result is that νc* (G) - νc (G) = o (n2) 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 (n2) in randomized polynomial time. Since computing νc (G) is an NP-Hard problem, and since almost all digraphs have νc (G) = Θ (n2) our result is a FPTAS for computing νc (G) for almost all digraphs. The 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 νF (G) denote the maximum number of arc-disjoint copies of elements of F 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) dicycles receiving nonzero weight can be found in polynomial time.

שפה מקוריתאנגלית
עמודים (מ-עד)82-91
מספר עמודים10
כתב עתDiscrete Applied Mathematics
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 15 ינו׳ 2007

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Packing directed cycles efficiently'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי