On integrality, stability and composition of dicycle packings and covers

Given a digraph D, the minimum integral dicycle cover problem (known also a s the minimum feedback arc set problem) is to find a minimum set of arcs th at intersects every dicycle; the maximum integral dicycle packing problem i s to find a maximum set of pairwise arc disjoint dicycles. These two proble ms 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) o f the corresponding pieces. The composition of the covers is simple and was partially considered in the literature before. The main contribution of th is paper is to the packing problem. Let tau be the value of a minimum integ ral dicycle cover, and nu* (nu) the value of a maximum (integral) dicycle p acking. We show that if tau = nu then a simple composition, similar to that of the covers, is valid for the packing problem. We use these compositions to extend an O(n(3)) (resp., O(n(4))) algorithm for finding a minimum inte gral dicycle cover (resp., packing) from planar digraphs to K-3,K-3-free di graphs (i.e., digraphs not containing any subdivision of K-3,K-3). However, if tau not equal nu, then such a simple composition for the packin g 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 nu = nu* holds for each piece, then the stability property holds as well . Further, we use the stability property to show that if nu = nu* holds for each piece, then nu = nu(*) holds for D as well.