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 ω. 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) ≤ ω(e) for each e ∈ E(G). The fractional dicycle packing number, denoted νc*l(G, ω), is the maximum value of ∑C∈C ψ(C) taken over all fractional dicycle packings ψ. In case ω = 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) = Θ(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 ℱ be any fixed family of oriented graphs. For an oriented graph G, let ν(G) denote the maximum number of arc-disjoint copies of elements of ℱ that can be found in G, and let ν*(G) denote the fractional relaxation. Then, ν*(G) - ν(G) = o(n2). This lemma uses the recently discovered directed regularity lemma as its main tool. It is well known that νc*(G, ω) 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*(G,w) can be generated in polynomial time. We prove that a maximum fractional dicycle packing yielding νc*(G, ω) with at most O(n2) dicycles receiving nonzero weight can be found in polynomial time.

שפה מקוריתאנגלית
כותר פרסום המארחLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
עורכיםJirí Fiala, Jan Kratochvíl, Vá clav Koubek
מוציא לאורSpringer Verlag
מספר עמודים12
מסת"ב (אלקטרוני)3540228233, 9783540228233
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2004

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349

טביעת אצבע

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

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