DFK Consult

This is a series of posts about the Dinitz-Garg-Goemans (DGG) conjecture, which describes a very special issue in many industrial areas. The first post describes the current situation.

For the license information goto part 1.

By translating the architectural crisis into pure graph-theoretic terms, the paper provides a decisive structural remedy. It completely replaces empirical trial-and-error with analytical certainty, executing this shift in two distinct, powerful phases.

---

1. The Algebraic Falsification: A Definite Boundary for Structural Designers

The first major contribution of the newly on Zenodo published paper is the formal, algebraic falsification of the 1999 Dinitz-Garg-Goemans (DGG) cost conjecture for the Single-Source Unsplittable Flow Problem (SSUFP).

The Structural Proof Mechanism

The paper constructs an exact, asymmetric topological graph containing a source $s$, two distinct terminals $t_1, t_2$, and a critical central edge $e_{\text{mid}}$ with capacity $u_{\text{mid}} = d$ and low routing cost $c_{\text{mid}} = L$.

It algebraically proves that under a continuous, fractional flow model, the total system cost is bounded perfectly at:

However, when the demands are atomized and unsplittable, any purely spatial routing algorithm faces a geometric trap. To avoid overloading the main bottleneck, the system must divert the second unsplittable flow to an alternative peripheral path $e_{\text{out2}}$ characterized by an unconstrained, highly punitive environmental cost variable $H$.

The paper calculates the exact optimal ununsplit cost under static constraints as:

$C_{\text{unsplit}}=d\cdot (L+H)$

By evaluating the competitive ratio $\rho$ between the discrete unteilbar flow and the ideal fractional baseline, the paper extracts the definitive ratio:

$\rho =\frac{C_{\text{unsplit}}}{C_{\text{frac}}}=\frac{d(L+H)}{2dL}=\frac{1}{2}+\frac{H}{2L}$

The Systemic Realization

Because $H$ is a variable dictated by external, unconstrained environmental factors (such as the physical length of an outer bypass or the extreme latency of a secondary network), it can grow arbitrarily large. As a consequence:

$\lim _{H\rightarrow \infty }\rho =\infty$

The Architectural Breakthrough

This mathematical limit serves as an absolute „Stop Sign“ for software engineers and network architects. It mathematically proves that it is impossible to design a purely spatial routing algorithm that prevents infinite cost or latency explosion in an unsplittable network containing asymmetric dead-ends.

Knowing this, engineering teams can instantly stop wasting R&D capital on building increasingly complex spatial heuristics. The paper proves that the fault lies not within the quality of the heuristic, but within the physics of a purely spatial graph.

---

2. The Time-Buffer Theorem: Immunizing Networks Against Spatial Penalties

To fix the structural vulnerability exposed by the falsification, the paper expands the spatial graph $G = (V, E)$ into a dynamic, time-expanded network by introducing a temporal dimension $T = \{t_0, t_1, \dots\}$.

The mathematical core of this solution is the introduction of a specialized local loop directly at the source node: the Storage Arc (or Time-Buffer), denoted as $e_{\text{buffer}}$.

+-----------------------------------------------------------------------------+
|                          TEMPORAL ORTHOGONALIZATION                         |
+-----------------------------------------------------------------------------+
|                                                                             |
|      [Source s] ---( Local Time Puffer e_buffer, Cost P )---+               |
|          |                                                  | (Loop back)   |
|          +<-------------------------------------------------+               |
|          |                                                                  |
|          v                                                                  |
|  [Main Bottleneck e_mid (Capacity u = d, Spatial Cost L)]                   |
|          |                                                                  |
|          +---------> Time Step t_0: Flow 1 passes e_mid                     |
|          |           (Flow 2 circles in e_buffer)                           |
|          |                                                                  |
|          +---------> Time Step t_1: Flow 2 passes e_mid                     |
|                      (e_mid is now clear and empty)                         |
|                                                                             |
+-----------------------------------------------------------------------------+

The Mechanism of Temporal Orthogonalization

Instead of resolving a capacity conflict by pushing the competing flow outward into space (the expensive detour $H$), the Time-Buffer Theorem resolves the conflict by pushing the flow forward into time.

• At Time Step $t_{0}$: Flow 1 is granted immediate access to the high-efficiency central bottleneck $e_{\text{mid}}$, incurring a cost of $d \cdot L$. Simultaneously, Flow 2 is held back, entering the local storage arc $e_{\text{buffer}}$. It remains stationary at the source, paying a minimal temporal holding fee $P$ (where $P \ll H$).
• At Time Step $t_{1}$: Flow 1 has entirely cleared the main bottleneck, leaving $e_{\text{mid}}$ empty. Flow 2 exits the storage arc and enters the now vacant bottleneck, traversing it at the low cost of $d \cdot L$.

The Mathematical Proof of Convergence

The paper aggregates the total cost of this time-buffered, unsplittable allocation ($C_{\text{unsplit\_time}}$) as follows:

$C_{\text{unsplit\_time}}=d\cdot L+d\cdot P+d\cdot L=2d\cdot L+d\cdot P$

When we calculate the new dynamic competitive ratio ($\rho _{\text{time}}$) against the fractional baseline, the true power of the theorem emerges:

$\rho _{\text{time}}=\frac{C_{\text{unsplit\_time}}}{C_{\text{frac}}}=\frac{2dL+dP}{2dL}=1+\frac{P}{2L}$

Eliminating the Worst-Case Risk

We now re-evaluate the system under the exact same extreme stress test where the spatial detour cost $H$ escalates to infinity:

$\lim _{H\rightarrow \infty }\left(1+\frac{P}{2L}\right)=1+\frac{P}{2L}<\infty$

Because the unconstrained variable $H$ is completely missing from the dynamic cost function, the total operational cost of the system is entirely immunized against external spatial penalties.

---

3. The New Engineering Paradigm: Exact Dimensioning

For system designers, this theorem completely replaces empirical estimation with deterministic calculation:

3.1 Deterministic Guarantees: If an industrial plant can tolerate a maximum cost or latency overhead of 10% above the theoretical minimum ($\rho_{\text{time}} = 1.1$), the engineer no longer needs to guess the buffer size. They simply plug the values into the verified formula and solve for $P$:

$1+\frac{P}{2L}=1.1\implies P=0.2\cdot L$

The engineer now has a rigorous mathematical proof that as long as the cost of the time buffer is kept below 20% of the main line’s cost, the system will never experience an un-bounded cost explosion.

3.2 Elimination of Computational Overhead: Because the routing choice is no longer an open-ended, global optimization problem involving infinite spatial paths, the computational complexity drops drastically. The system only needs to evaluate a local binary decision: Should I route spatially now, or buffer temporally for $\Delta t$?

---

cheers