On Integrality, Stability and Composition of Dicycle Packings and Covers

Zeev Nutov, Michal Penn

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء


Given a digraph D, the minimum integral dicycle cover problem (known also as the minimum feedback arc set problem) is to find a minimum set of arcs that intersects every dicycle; the maximum integral dicycle packing problem is to find a maximum set of pairwise arc disjoint dicycles. These two problems are NP-complete. Assume D has a 2-vertex cut. We show how to derive a minimum dicycle cover (a maximum dicycle packing) for D, by composing certain covers (packings) of the corresponding pieces. The composition of the covers is simple and was partially considered in the literature before. The main contribution of this paper is to the packing problem. Let τ be the value of a minimum integral dicycle cover, and ν* (ν) the value of a maximum (integral) dicycle packing. We show that if τ = ν then a simple composition, similar to that of the covers, is valid for the packing problem. We use these compositions to extend an O (n3) (resp., O (n4)) algorithm for finding a minimum integral dicycle cover (resp., packing) from planar digraphs to K3,3-free digraphs (i.e., digraphs not containing any subdivision of K3,3). However, if τ ≠ ν, then such a simple composition for the packing problem is not valid. We show, that if the pieces satisfy, what we call, the stability property, then a simple composition does work. We prove that if ν = ν* holds for each piece, then the stability property holds as well. Further, we use the stability property to show that if ν = ν* holds for each piece, then ν = ν* holds for D as well.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)235-251
عدد الصفحات17
دوريةJournal of Combinatorial Optimization
مستوى الصوت4
رقم الإصدار2
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2000
منشور خارجيًانعم

ملاحظة ببليوغرافية

Funding Information:
Partial support was received from the fund for the promotion of research at the Technion. The authors are indebted to the referees for their valuable comments.


أدرس بدقة موضوعات البحث “On Integrality, Stability and Composition of Dicycle Packings and Covers'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا