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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2004

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت3153
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349


أدرس بدقة موضوعات البحث “Packing directed cycles efficiently'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا