On Packing Dijoins in Digraphs and Weighted Digraphs
Ahmad Abdi, Gérard Cornuéjols, Michael Zlatin · SIAM Journal on Discrete Mathematics · 2023
Abstract. Let [Formula: see text] be a digraph. A dicut is a cut [Formula: see text] for some nonempty proper vertex subset [Formula: see text] such that [Formula: see text], a dijoin is an arc subset that intersects every dicut at least once, and more generally a [Formula: see text]- dijoin is an arc subset that intersects every dicut at least [Formula: see text] times. Our first result is that [Formula: see text] can be partitioned into a dijoin and a [Formula: see text]-dijoin where [Formula: see text] denotes the smallest size of a dicut. Woodall conjectured the stronger statement that [Formula: see text] can be partitioned into [Formula: see text] dijoins. Let [Formula: see text], and suppose every dicut has weight at least [Formula: see text], for some integer [Formula: see text]. Let [Formula: see text], where each [Formula: see text] is the integer in [Formula: see text] equal to [Formula: see text] mod [Formula: see text]. We prove the following results: If [Formula: see text], then there is an equitable [Formula: see text]-weighted packing of dijoins of size [Formula: see text]. If [Formula: see text], then there is a [Formula: see text]-weighted packing of dijoins of size [Formula: see text]. If [Formula: see text], [Formula: see text], and [Formula: see text], then [Formula: see text] can be partitioned into three dijoins. Each result is best possible: (i) does not hold for [Formula: see text] even if [Formula: see text], (ii) does not hold for [Formula: see text], and (iii) does not hold for general [Formula: see text].