Strongly Connected Orientations and Integer Lattices

Let $D=(V,A)$ be a digraph whose underlying undirected graph is two-edge connected, and let P be the polytope whose vertices are the incidence vectors of arc sets whose reversal makes D strongly connected. We study the lattice-theoretic properties of the integer points contained in a proper face F of P not contained in $\{x:x_a=i\}$ for any $a\in A,i\in \{0,1\}$. We prove under a mild necessary condition that $F\cap {\{0,1\}}^A$ contains an integral basis B (i.e., B is linearly independent) and any integral vector in the linear hull of F is an integral linear combination of B. This result is surprising as the integer points in F do not necessarily form a Hilbert basis. In proving the result, we develop a theory similar to matching theory for degree-constrained dijoins in bipartite digraphs. Our result has consequences for head-disjoint strong orientations in hypergraphs and also, to a famous conjecture by Woodall that the minimum size of a dicut of D, say $\tau$, is equal to the maximum number of disjoint dijoins. We prove a relaxation of this conjecture by finding for any prime number $p\ge 2$, a p-adic packing of dijoins of value $\tau$ and of support size at most $2|A|$. We also prove that the all-ones vector belongs to the lattice generated by $F\cap {\{0,1\}}^A$, where F is the face of P satisfying $x({\delta }^{+}(U))=1$ for every dicut ${\delta }^{+}(U)$ with minimum size.

Funding: This research was supported by the Office of Naval Research [Grant N00014-22-1-2528] and the Engineering and Physical Sciences Research Council [Grant EP/X030989/1].