Source-linked AI summary
Independence-System Realisations in Single-Source Unsplittable Flow
Koyar Afrasyab
TL;DR
The paper addresses how additive-congestion inequalities can encode independence systems while remaining valid for every actual source-terminal path. It defines strong realisation and builds acyclic gadgets using private zero-cost chains, incidence resources, auxiliary demands, and exact rational certificates. For the odd-cycle instance, 1-good cheap selections are exactly the stable sets of Cn, and its threshold satisfies τ⋆ = 1 − t < (k + 2)/(2(k + 1)).
Problem
The paper addresses how additive-congestion inequalities can encode independence systems while remaining valid for every actual source-terminal path.
Method
It defines strong realisation and builds acyclic gadgets using private zero-cost chains, incidence resources, auxiliary demands, and exact rational certificates.
Results
For the odd-cycle instance, 1-good cheap selections are exactly the stable sets of Cn, and its threshold satisfies τ⋆ = 1 − t < (k + 2)/(2(k + 1)).
Takeaways & Limitations
Stable-set and hypergraph independence constraints can be represented by ordinary additive-load inequalities in acyclic single-source flow gadgets.
Takeaways & Limitations
The threshold result is restricted to the uniform symmetric odd-cycle family, and the universal theorem is not formalised in a proof assistant.
Abstract
from arXiv · showhide
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 routes.Our 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.
1 Introduction
The note generalises a triangle-based conflict mechanism into a path-closed framework for encoding independence systems through additive-congestion constraints. It also positions the result relative to prior rounding guarantees and the reproduced triangle counterexample.
- Introduction: The reproduced seven-vertex triangle has fractional cost 58, while every additive-15-good unsplittable routing costs at least 60, refuting the cost-preserving additive-D conjecture in this audited instance.The independent verifier derives all six source-terminal paths and checks all eight routings; the graph is planar and acyclic.
- Main contributions: Strong realisation quantifies over every actual directed path, making the encoding robust to prefix borrowing, suffix splicing, and hybrid routes.This path-closure requirement addresses the fact that a graph may create routes beyond any prescribed menu.
- Main contributions: Every finite loopless independence system can be strongly realised by an acyclic single-source unsplittable-flow instance, with size linear in ground-set size plus forbidden-set incidence size.The construction generalises stable-set encoding beyond triangles, but its size depends on an explicit minimal-forbidden-set representation.
- Scope: The odd-cycle family generalises the stable-set mechanism and determines a scoped cost-preserving threshold, but does not strengthen the triangle refutation or establish a universal barrier.The paper presents the result as a research note and limits novelty and priority claims.
3 Model and definitions
The model studies fractional and unsplittable single-source flows with additive arc-load guarantees, and defines cheap primary selections through zero-cost paths. Strong realisation requires the selected sets to coincide exactly with an independence system under all actual graph paths.
- Model: A fractional flow may split each terminal demand across paths, whereas an unsplittable routing chooses one source-terminal path per terminal.Additive goodness compares the resulting arc loads with fractional loads plus an additive demand allowance.
- Definitions: A primary terminal is selected exactly when its chosen path has total cost zero.Primary terminals are indexed by the ground set, while auxiliary terminals support the conflict encoding.
- Strong realisation: Strong realisation requires every independence-system set to be selectable by a 1-good routing and forbids every non-independent selected set.The definition quantifies over all directed source-terminal paths rather than a prescribed decomposition.
- Definitions: Looplessness means every singleton is independent, equivalently that every minimal forbidden set has at least two elements.Independent sets are exactly those containing no minimal forbidden set.
4 A universal realisation theorem
The universal gadget assigns private zero-cost chains to decisions and incidence resources to minimal obstructions, with auxiliary demands enforcing forbidden-set conflicts. Exit domination and unique cheap paths establish correctness under all graph paths.
- Construction: The construction uses one private decision chain per ground element, one incidence resource per element–forbidden-set participation, and one auxiliary terminal per minimal forbidden set.Acyclic ordering places the source first, private chain vertices left-to-right, and terminals last.
- Fractional flow: With q = 1/4 and unit terminal demands, selected primaries use their chains while auxiliaries split uniformly across forbidden-set incidences, yielding a feasible fractional flow with D = 1.For any independent set, auxiliaries can route through an unselected incidence, keeping every relevant integral load at most one and therefore within x + D.
- Path closure: Every path to an auxiliary terminal must traverse an incidence resource immediately before its final exit, so borrowed prefixes cannot bypass the enforced conflict.This exit-dominator property supplies the path-closure argument.
- Cheap selections: Each primary terminal has exactly one zero-cost path: its full private chain; direct arcs and downstream approaches are strictly positive-cost alternatives.No arcs from other chains or auxiliary terminals enter a primary chain.
- Consequences: The theorem yields a polynomial-size realisation in the explicit incidence description and implies strong realisability for every finite simple graph and suitable hypergraph independence system.The size bound is linear in ground-set size plus total minimal-forbidden-set incidence size.
- Correctness: Selecting every element of a minimal forbidden set forces an auxiliary to share an incidence resource with a selected primary, producing load 2 and violating 1-goodness.Conversely, every independent set admits a 1-good routing selecting exactly that set.
5 A uniform odd-cycle family
A uniform construction for odd cycles makes the universal conflict encoding quantitative: its cheap selections are exactly stable sets, while its fractional cheap-selection vector violates the odd-cycle inequality.
- Construction: The family uses primary chain incidences for the two adjacent cycle edges, connectors, private approaches, and edge auxiliaries split equally across endpoint incidences.Each incidence resource has fractional load t + 1/2, each connector has load t, and D = 1.
- Stable-set correspondence: The 1-good cheap selections of the constructed odd-cycle instance are exactly the stable sets of C_n.Adjacent selected primaries overload an edge-incidence resource, while stable selections route each edge auxiliary through an unselected endpoint.
- Fractional violation: Every primary has fractional cheap-selection coordinate q, and the vector (q, ..., q) violates the odd-cycle inequality.The violation is expressed by nq > k for n = 2k + 1.
6 Nonnegative costs and an exact threshold
A potential shift converts the signed connector separator into nonnegative arc costs while preserving fractional–integral cost differences. For the uniform odd-cycle family, the exact cost-preserving additive-congestion threshold is τ = 1 − t.
- Nonnegative costs: A signed connector weight is transformed into nonnegative reduced costs by assigning potentials before and after each connector.The resulting costs place 1/b on direct primary arcs, approaches to second incidences, and exits from first incidences; all other arcs cost zero.
- Nonnegative costs: The potential terms cancel because fractional and integral routings have identical divergence, so the reduced-cost comparison preserves the original cost difference.This establishes the cost-preserving use of the nonnegative-cost construction.
- Exact threshold: Theorem 8 gives the exact threshold: every λ < 1 − t fails, while λ = 1 − t admits an unsplittable routing no more expensive than the fractional routing.The lower bound follows from borrowed auxiliary routes becoming infeasible below 1 − t; equality is achieved by routing primaries directly and borrowing prefixes for edge auxiliaries.
- Stable-set enforcement: If adjacent primaries were selected, an edge auxiliary would load an incidence resource at b + 1, exceeding the relevant bound; hence selected primaries form a stable set of size at most k.The displayed comparison establishes the contradiction for adjacent selections.
- Exact threshold: At λ = 1 − t, routing every primary directly and each edge auxiliary through a borrowed prefix yields routing cost n while satisfying the remaining bounds.The construction shows attainability of the threshold under t < 1/2.
7 Optimisation within the symmetric family
Within the uniform symmetric parameterisation, feasibility and odd-cycle violation impose competing inequalities on the parameters. Their balance yields a supremum threshold approaching 1/2 as the cycle grows.
- Constraints: The construction requires s0 > 1/2 for exact stable-set realisation, while odd-cycle violation requires nq > k.With t = bq and n = 2k + 1, these conditions determine the feasible optimisation range.
- Optimisation: The key parameter inequality is (k + 1)t > ks0 > k, which drives the upper bound τ⋆ < (k + 2)/(2(k + 1)).This bound is matched arbitrarily closely within the symmetric family.
- Optimisation: The supremum threshold is (k + 2)/(2(k + 1)) = 1/2 + 1/(2(k + 1)), and it tends to 1/2 as k increases.The threshold is approached as τ⋆ = (k + 2)/(2(k + 1)) − ε.
8 An exact C5 certificate
The C5 certificate independently verifies path structure, cheap-selection correspondence, and exact routing-cost claims using exhaustive rational-arithmetic checks.
- 8 An exact C5 certificate: The machine-readable DAG has 31 vertices and 45 arcs, with three actual paths for each of five primary and five auxiliary terminals.The verifier derives path sets from the arc list rather than trusting a prescribed decomposition, then enumerates all 3^10 = 59,049 routings.
- 8 An exact C5 certificate: The independent certificate checks fractional feasibility, acyclicity, zero-cost uniqueness, stable-set masks, and exact cost inequalities.Mutation tests reject changes that remove incompatibilities, add bypasses, create cheap hybrid primary routes, or erase the odd-cycle violation.
- 8 An exact C5 certificate: At λ = 1, exactly the 11 stable sets of C5 occur as cheap masks.The verifier also establishes exactly one zero-cost path for each primary terminal.
- 8 An exact C5 certificate: At λ = 7/12, the minimum integral cost is 151/17, exceeding cT x = 905/102 by exactly 1/102.
- 8 An exact C5 certificate: At τ⋆ = 79/120, the certificate finds a routing of cost 5 < cT x.
9 Discussion and limitations
The construction realizes broad independence-system structure, but its size and threshold claims remain explicitly scoped by representation and family limitations.
- 9 Discussion and limitations: The universal construction uses private zero-cost chains, incidence resources, auxiliary demands, and exit dominators to encode minimal forbidden sets robustly under path splicing.
- 9 Discussion and limitations: Construction size is polynomial in the explicit minimal-forbidden-set incidence description, which may itself be exponentially large.
- 9 Discussion and limitations: The exact threshold applies only to the uniform symmetric odd-cycle family and neither reaches the additive-D boundary nor establishes 1/2 as a universal barrier.
10 Conclusion
The paper concludes that path-closed additive-congestion constraints can represent finite independence systems, with odd cycles providing scoped quantitative results and C5 supplying a finite certificate.
- 10 Conclusion: Every finite loopless independence system can be embedded as the cheap-choice structure of an acyclic single-source unsplittable-flow instance closed under all actual graph paths.
- 10 Conclusion: Odd cycles turn the qualitative representation mechanism into a scoped cost-congestion calculation, while the C5 certificate demonstrates finite-scale reproducibility.
- 10 Conclusion: The paper proposes compressed gadgets and investigations of graph restrictions such as planarity, bounded genus, bounded treewidth, and series-parallel structure.
A Reproducibility protocol
The reproducibility package combines provenance-labelled instances, exact verifiers, symbolic checks, and adversarial mutation tests without third-party Python dependencies.
- A Reproducibility protocol: The package includes a reproduced triangle instance, the C5 JSON instance, exhaustive verifiers, and a symbolic parameter checker.
- A Reproducibility protocol: The suite enumerates all paths and routings for both finite certificates, checks parameter identities and inequalities for k = 1, . . . , 200, and runs adversarial mutation tests.It requires no third-party Python package.