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
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 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'. יחד הם יוצרים טביעת אצבע ייחודית.

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