Lattice Structure and Efficient Basis Construction for Strongly Connected Orientations
Siyue Liu, Olha Silina · 2026
Read Lattice Structure and Efficient Basis Construction for Strongly Connected Orientations by Siyue Liu, Olha Silina (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-17424.txt.
Introduction
Liu and Silina study strongly connected orientations of bidirected graphs. An orientation is tight when each set in a given family gets exactly one entering arc. They give a polynomial-time algorithm that builds an integral basis of tight orientations. Their proof is purely combinatorial, unlike an earlier polyhedral one. The method also solves parity-constrained versions in deterministic polynomial time. Links to perfect matching lattices appear along the way, they note.
Catalog record
| CREATOR | Siyue Liu, Olha Silina |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 131055 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.17424
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Lattice Structure and Efficient Basis Construction for Strongly Connected Orientations Siyue Liu, Olha Silina Abstract Let G → = ( V , E + ∪ E − ) \vec{G}=(V,E^{+}\cup E^{-}) be a bidirected graph whose underlying undirected graph G = ( V , E ) G=(V,E) is 2 2 -edge-connected. A strongly connected orientation (SCO) is defined as a subset of arcs that contains exactly one of e + , e − e^{+},e^{-} for every e ∈ E e\in E and induces a strongly connected subgraph of G → \vec{G} . Given a family ℱ \mathcal{F} of proper subsets of V V , we call an SCO tight if there is exactly one arc entering U U for every U ∈ ℱ 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 tight SCO’s. This means that ℬ \mathcal{B} is a linearly independent subset of tight SCO’s, and every integer vector in the linear hull of tight SCO’s can be written as an integral combination of ℬ \mathcal{B} . This extends the main result of Abdi, Conuéjols, Liu and Silina (IPCO 2025), who gave a non-constructive proof of the existence of such a basis in an equivalent setting. 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. 1 Introduction Given a 2 -edge-connected undirected graph G=(V,E) , its bidirected graph \vec{G}=(V,E^{+}\cup E^{-}) is obtained from copying every edge e\in E twice and orienting them in the opposite directions, denoted as e^{+}\in E^{+} and e^{-}\in E^{-} . Here, E^{+} and E^{-} are two arbitrary orientations of E that are opposite to each other. A strongly connected orientation (SCO) is an arc subset \vec{E}\subseteq E^{+}\cup E^{-} which contains exactly one of e^{+},e^{-} for every e\in E , and satisfies |\delta_{\vec{E}}^{-}(U)|\geq 1 for every \emptyset\neq U\subsetneqq V . In this work, we consider a class of SCO’s restricted by a family \mathcal{F}\subseteq 2^{V}\setminus\{\emptyset,V\} of proper subsets of V . Given \mathcal{F} , we say an SCO \vec{E} is tight for (G,\mathcal{F}) if for every U\in\mathcal{F} there is exactly one arc coming into U , i.e., |\delta_{\vec{E}}^{-}(U)|=1 . We denote by \sco(G,\mathcal{F}) the set of tight SCO’s of (G,\mathcal{F}) . We study the lattice of tight strongly connected orientations , i.e., the lattice generated by the indicator vectors of tight SCO’s, denoted by \lat(\sco(G,\mathcal{F})) . Denote by \lin(\sco(G,\mathcal{F})) the linear hull of tight SCO’s. It is easy to see that \lat(\sco(G,\mathcal{F}))\subseteq\lin(\sco(G,\mathcal{F}))\cap\mathbb{Z}^{A} . Given a rational linear subspace L\subseteq\mathbb{R}^{E^{+}\cup E^{-}} , an integral basis for L is a subset \mathcal{B}\subseteq L\cap\mathbb{Z}^{E^{+}\cup E^{-}} of linearly independent vectors such that every vector in L\cap\mathbb{Z}^{E^{+}\cup E^{-}} can be written as an integral linear combination of \mathcal{B} . Since the dimension of \lin(\sco(G,\emptyset)) is at most |E| , there are at most |E| many sets U\in\mathcal{F} for which the constraints |\delta_{\vec{E}}^{-}(U)|=1 are linearly independent. Thereby we may assume w.l.o.g. that |\mathcal{F}|\leq|E| , which implies the input size (G,\mathcal{F}) is bounded by the size of the graph. Our main result is the following: Theorem 1.1 . Let G=(V,E) be a 2 -edge-connected undirected graph. For an arbitrary \mathcal{F}\subseteq 2^{V}\setminus\{\emptyset,V\} with |\mathcal{F}|\leq|E| , we can construct an integral basis for \lin(\sco(G,\mathcal{F})) consisting of tight SCO’s in polynomial time. This result implies two things: first, \lat(\sco(G,\mathcal{F}))=\lin(\sco(G,\mathcal{F}))\cap\mathbb{Z}^{E^{+}\cup E^{-}} ; second, there is a basis for \lat(\sco(G,\mathcal{F})) that consists of tight SCO’s. This result is essentially the algorithmic counterpart of Abdi, Conuéjols, Liu and Silina [ 3 ] , who gave a non-constructive proof of the same result in terms of strongly connected reorientations (SCR) , or strengthenings in digraphs. In a digraph, a subset of arcs is a strengthening if the digraph obtained from flipping the arcs in J is strongly connected. Given a family \mathcal{F}\subseteq 2^{V}\setminus\{\emptyset,V\} , we say a strengthening J is tight for (D,\mathcal{F}) if after flipping the arcs of J , there is exactly one arc coming into every U\in\mathcal{F} . Denote by \scr(D,\mathcal{F}) the set of tight strengthenings of (D,\mathcal{F}) . The main result of [ 3 ] is the following: Theorem 1.2 ( [ 3 ] ) . Let D=(V,A) be a digraph whose underlying undirected graph is 2 -edge-connected. Let \mathcal{F}\subseteq 2^{V}\setminus\{\emptyset,V\} such that |\mathcal{F}|\leq|A| and \gcd\{1-|\delta^{-}(U)|:U\in\mathcal{F}\}=1 . Then there exists an integral basis for \lin(\scr(D,\mathcal{F})) consisting of tight strengthenings. One can easily go between tight strengthenings in a digraph D=(V,A) and tight SCO’s in the bidirected graph \vec{G}=(V,A\cup A^{-1}) , where A^{-1} are the reverse arcs of A , via an invertible linear transformation, so our main Theorem 1.1 implies Theorem 1.2 (we prove this in Appendix A ). The proof in [ 3 ] is an existence proof obtained from studying the implicit equalities and facets of the polytope of tight strengthenings. The main contribution of this paper is developing a new combinatorial proof which leads to a polynomial-time algorithm to construct such a basis. Our main motivation for studying tight strengthenings is the following conjecture by Woodall [ 48 ] . In a digraph, a dicut is the set of arcs leaving a nonempty proper vertex subset with no incoming arcs, i.e., an arc set of the form \delta^{+}(U) for some \emptyset\neq U\subsetneqq V such that \delta^{-}(U)=\emptyset . A dijoin is an arc subset that intersects every dicut at least once. In order to make the digraph strongly connected, at least one arc from each dicut has to be flipped, and thus, every strengthening is a dijoin. Woodall conjectured that the maximum number of disjoint dijoins is equal to the minimum size of a dicut. Schrijver [ 44 ] reformulated Woodall’s conjecture in the following: Conjecture 1.3 ( [ 44 ] ) . Let \tau\geq 2 be an integer, and let D=(V,A) be a digraph where the minimum size of a dicut is \tau . Then A can be partitioned into \tau strengthenings. Observe that if such a statement were true, the only strengthenings allowed in a partition would be the ones that intersect every dicut of size \tau exactly once. Therefore, it suffices to restrict ourselves to those strengthenings, which are precisely \scr(D,\mathcal{F}) for \mathcal{F} being the family of sets U\subseteq V that induce dicuts \delta^{+}(U) of size \tau . Theorem 1.2 implies a relaxation of 1.3 that allows adding and subtracting tight strengthenings [ 3 ] . Formally, it implies that we can find an assignment \lambda_{J}\in\mathbb{Z} to every strengthening J that intersects every minimum dicut exactly once such that \sum_{J}\lambda_{J}\mathbf{1}_{J}=\mathbf{1}_{A} and \sum_{J}\lambda_{J}=\tau . As a new application, we address the parity strongly connected orientation (SCO) problem. Given a 2 -edge-connected undirected graph G=(V,E) , its bidirected graph \vec{G}=(V,E^{+}\cup E^{-}) is obtained from copying every edge e\in E twice and orienting them in the opposite directions, denoted as e^{+}\in E^{+} and e^{-}\in E^{-} . Let \mathcal{F}\subseteq 2^{V}\setminus\{\emptyset,V\} and let R\subseteq E^{+}\cup E^{-} be a subset of red arcs. We define the parity strongly connected orientation (SCO) problem as follows: Parity strongly connected