Leírás
Let $D=(V,A)$ be a digraph whose underlying undirected graph is $2$-edge-connected. A subset of arcs $J\subseteq A$ is a strengthening if reversing the arcs of $J$ makes $D$ strongly connected. Given a family $\mathcal{F}$ of proper subsets of $V$, we call a strengthening $J$ tight if after flipping $J$, there is exactly one arc entering $U$ for every $U\in \mathcal{F}$. We give a polynomial time-algorithm to construct a set $\mathcal{B}$ consisting of tight strengthenings which forms an integral basis for the linear hull of tight strengthenings, i.e., $\mathcal{B}$ is a linearly independent subset of tight strengthenings, and every integer vector in the linear hull of tight strengthenings can be written as an integral combination of $\mathcal{B}$. This extends the main result of Abdi, Cornu\'ejols, Liu, and Silina (IPCO 2025), who gave a non-constructive proof of the existence of such a basis. While their proof uses polyhedral theory, our proof is purely combinatorial and yields a polynomial-time algorithm. As an application of our algorithm, we show that parity-constrained tight strongly connected orientation can be solved in deterministic polynomial time. Along the way, we discover appealing connections to the theory of perfect matching lattices.