{"id":"arxiv/2603.17424","url":"https://arxiv.org/abs/2603.17424","tags":["math.CO","cs.DS"],"score":0,"title":"Lattice Structure and Efficient Basis Construction for Strongly Connected Orientations","domain":"math.CO","source":"arxiv","authors":["Siyue Liu","Olha Silina"],"reviews":0,"subject":"math.CO","summary":"Let $\\vec{G}=(V,E^+\\cup E^-)$ be a bidirected graph whose underlying undirected graph $G=(V,E)$ is $2$-edge-connected. A strongly connected orientation (SCO) is defined as a subset of arcs that contains exactly one of $e^+,e^-$ for every $e\\in E$ and induces a strongly connected subgraph of $\\vec{G}$. Given a family $\\mathcal{F}$ of proper subsets of $V$, we call an SCO tight if 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 SCO's which forms an integral basis for the linear hull of…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-18","reactions":{}}