On Integrality, Stability and Composition of Dicycle Packings and Covers

Zeev Nutov () and Michal Penn ()
Additional contact information
Zeev Nutov: Max-Planck-Institut für Informatik
Michal Penn: Faculty of Industrial Engineering and Management, Technion

Journal of Combinatorial Optimization, 2000, vol. 4, issue 2, No 6, 235-251

Abstract: Abstract 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.

Keywords: graph; integral dicycle cover; integral dicycle packing; 3-connected-component; composition; K3; 3-free digraph (search for similar items in EconPapers)
Date: 2000
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1009802905533 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:4:y:2000:i:2:d:10.1023_a:1009802905533

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009802905533

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().