Independence-System Realisations in Single-Source Unsplittable Flow

Abstract:Additive-congestion constraints in single-source unsplittable flow can enforce stable-set structure. This note isolates and generalises that mechanism. We introduce a path-closed notion of realising an independence system by the zero-cost choices of primary terminals in a directed acyclic flow instance. The definition quantifies over every directed source-terminal path and therefore remains valid under prefix borrowing, suffix splicing, and hybrid this http URL main result extends the triangle mechanism: every finite loopless independence system has a polynomial-size realisation, measured in the incidence size of its minimal forbidden sets. Hence every finite simple graph, and more generally every hypergraph independence system without singleton forbidden hyperedges, is representable by an acyclic single-source gadget. We then specialise the construction to odd cycles. For C_{2k+1}, a uniform rational family produces a fractional cheap-selection vector that violates the odd-cycle inequality. A potential shift converts a signed connector separator into nonnegative arc costs and gives the exact cost-preserving additive-congestion threshold tau = 1 - bq. Within the symmetric family, the supremum threshold is (k+2)/(2(k+1)), which tends to 1/2. For C5, an exact certificate independently derives all source-terminal paths and enumerates all 3^10 = 59049 unsplittable routings using rational arithmetic.

Data Structures and Algorithms (cs.DS); Artificial Intelligence (cs.AI)

arXiv:2609.17568 [cs.DS]

(or arXiv:2609.17568v1 [cs.DS] for this version)

https://doi.org/10.48550/arXiv.2609.17568 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.