On packing dijoins in digraphs and weighted digraphs

Abstract

Let $D=(V,A)$ be a digraph. A dicut is a cut ${\delta }^{+}(U)\subseteq A$ for some nonempty proper vertex subset $U$ such that ${\delta }^{-}(U)=\varnothing$, a dijoin is an arc subset that intersects every dicut at least once, and more generally a $k$-dijoin is an arc subset that intersects every dicut at least $k$ times. Our first result is that $A$ can be partitioned into a dijoin and a $(\tau -1)$-dijoin where $\tau$ denotes the smallest size of a dicut. Woodall conjectured the stronger statement that $A$ can be partitioned into $\tau$ dijoins. Let $w\in {\mathbb{Z}}_{\ge 0}^A$ and suppose every dicut has weight at least $\tau$, for some integer $\tau \ge 2$. Let $\rho (\tau ,D,w):=\frac{1}{\tau }{\sum }_{v\in V}{m}_v$, where each $m_v$ is the integer in $\{0,1,\dots ,\tau -1\}$ equal to $w({\delta }^{+}(v))-w({\delta }^{-}(v))$ mod $\tau$. We prove the following results: (i) If $\rho (\tau ,D,w)\in \{0,1\}$, then there is an equitable $w$-weighted packing of dijoins of size $\tau$. (ii) If $\rho (\tau ,D,w)=2$, then there is a $w$-weighted packing of dijoins of size $\tau$. (iii) If $\rho (\tau ,D,w)=3$, $\tau =3$, and $w=1$, then $A$ can be partitioned into three dijoins. Each result is best possible: (i) does not hold for $\rho (\tau ,D,w)=2$ even if $w=\1$, (ii) does not hold for $\rho (\tau ,D,w)=3$, and (iii) do not hold for general $w$.

69 pages, 15 figures