TY - JOUR
T1 - On Integrality, Stability and Composition of Dicycle Packings and Covers
AU - Nutov, Zeev
AU - Penn, Michal
N1 - 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.
PY - 2000
Y1 - 2000
N2 - 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.
AB - 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.
KW - 3-connected-component
KW - Composition
KW - Graph
KW - Integral dicycle cover
KW - Integral dicycle packing
KW - K-free digraph
UR - http://www.scopus.com/inward/record.url?scp=0042184017&partnerID=8YFLogxK
U2 - 10.1023/A:1009802905533
DO - 10.1023/A:1009802905533
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:0042184017
SN - 1382-6905
VL - 4
SP - 235
EP - 251
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 2
ER -