On Integrality, Stability and Composition of Dicycle Packings and Covers

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.