Strongly Connected Orientations and Integer Lattices
Ahmad Abdi, Gérard Cornuéjols, Siyue Liu, Olha Silina · Lecture notes in computer science · 2025
Abstract Let $$D\,=\,(V,A)$$ D = ( V , A ) be a digraph whose underlying graph is 2-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\}$$ { x : x a = i } for any $$a\in A,i\in \{0,1\}$$ a ∈ A , i ∈ { 0 , 1 } . We prove under a mild necessary condition that $$F\cap \{0,1\}^A$$ F ∩ { 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$$ p ≥ 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$$ F ∩ { 0 , 1 } A , where F is the face of P satisfying $$x(\delta ^+(U))=1$$ x ( δ + ( U ) ) = 1 for every minimum dicut $$\delta ^+(U)$$ δ + ( U ) .