2024/10/17 by Ahmad Abdi, Abdi, Ahmad, Gérard Cornuéjols +5 · 2 citations
Computer Science · Engineering · #05-XX #90-XX #Advanced Algebra and Logic #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Control (math.OC) #graph theory and CDMA systems
paper · doi:10.48550/arxiv.2410.13665
openalex publication_date 2024/10/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let D=(V,A) be a digraph whose underlying undirected 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:xa=i\ for any a∈ A,i∈ \0,1\. We prove under a mild necessary condition that 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 τ, is equal to the maximum number of disjoint dijoins. We prove a relaxation of this conjecture, by finding for any prime number p≥ 2, a p-adic packing of dijoins of value τ and of support size at most 2|A|. We also prove that the all-ones vector belongs to the lattice generated by F∩ \0,1\A, where F is the face of P satisfying x(δ+(U))=1 for every dicut δ+(U) with minimum size.