Research conclusion

I did not obtain a valid counterexample, and presenting the construction below as one would be mathematically false. The requested object would disprove a conjecture that is still open in the current literature.

The exact conjecture asks, for $D=d_{\max}$, for an unsplittable load vector $y$ satisfying

This is precisely Conjecture 1.3 in the supplied paper.

Dinitz_Garg_Goemans

The paper’s planar result does not prove this exact statement: with costs it obtains additive error $2D$, rather than $D$.

Dinitz_Garg_Goemans

As of July 2026, the latest SOSA work still describes the general statement as a famous conjecture with only limited progress; the exact result is now known for series-parallel digraphs, but not for arbitrary acyclic digraphs. epubs.siam.org+1

What follows is the strongest structured attack I found: an exact certificate formulation, a very small abstract almost-counterexample, and a rigorous explanation of why its natural graph realization fails.

1. An exact certificate for a genuine counterexample

Fix $G,s,T,d,x$, and let $\mathcal U$ be the finite set of load vectors of all unsplittable routings. Define the capacity-good routings by

Consider the linear program

This is a complete, machine-checkable test:

Indeed, if the optimum is $\delta>0$, its vector $c$ satisfies

for every capacity-good unsplittable routing. Conversely, any counterexample cost can be normalized so that $\sum_a c_a=1$, and the minimum gap over the finite set $\mathcal U(x)$ is strictly positive.

For an acyclic graph this is also a convex-hull test:

The reason is that every member of $\mathcal U(x)$ and $x$ has the same divergence. If $x$ were only componentwise above a convex combination of good routings, their difference would be a nonnegative circulation; an acyclic digraph has no nonzero nonnegative circulation.

Thus a publishable counterexample can be very compactly certified by giving rational data $G,d,x$ and a rational feasible solution of (SEP) with $\delta>0$.

2. A seven-resource structured almost-counterexample

Take three terminals with demands

For each terminal $i$, introduce two abstract choices $P_i^0,P_i^1$, and fractionally select each with probability $1/2$.

For every binary vector

introduce a resource $e_r$, and put $e_r$ in exactly the three choices

Let

Every resource has fractional load

An integral selection is represented by a binary vector $q$. Whenever $q\ne(1,1,1)$, the three selected choices all use $e_q$, giving load

But

and therefore

Consequently, every selection other than $111$ violates an upper bound. The selection $111$ is the unique capacity-good selection.

Now add a private cost-one resource to each choice $P_i^1$, while all other resources have cost zero. The fractional cost is

whereas the unique good selection $111$ costs

Thus, as an abstract partition-constrained resource-selection system, this is a clean counterexample with factor-two cost separation.

It is the seven-resource refinement of the cube construction in Figure 1 of the supplied paper. In the paper’s eight-resource version, every one of the eight binary selections overloads its corresponding black arc.

Dinitz_Garg_Goemans

3. Why it is not an SSUF counterexample

The obstruction is path splicing.

Suppose two intended paths contain a common directed segment,

Whenever the concatenations remain directed paths, the same support graph also contains

At the tail of $R$, the graph forgets which prefix was used; at the head of $R$, either available suffix may be taken. Repeated shared-resource gadgets therefore generate many hybrid paths that are not among the six designated choices.

This is not a cosmetic defect. Apply the Dinitz–Garg–Goemans theorem to the support graph

The same $x$ is a feasible fractional flow in $H$, so there must be an unsplittable routing entirely in $H$ satisfying $y\le x+D$. Therefore, any attempted realization of the seven-resource system must introduce enough support hybrids to repair its abstract capacity obstruction.

In a faithful layered reconstruction of the cube gadget, I obtained hundreds of actual source-terminal paths rather than two paths per terminal. The separating LP then had value $0$: hybrid routings restored the conjectured cost bound.

This also proves a useful no-go statement:

Off-support penalty lemma. A counterexample cannot assign zero cost to every arc with $x_a>0$ and try to penalize only newly introduced or off-support hybrid arcs.

The DGG routing obtained inside the support would then have cost zero, equal to the fractional cost.

4. Further necessary properties of a real counterexample

Unequal demands are indispensable

When all demands equal $d$, set $z=x/d$ and give arc $a$ the integral capacity

The fractional unit-demand flow $z$ is feasible for these capacities. By min-cost flow integrality, there is an integral flow $z'$ of no greater cost. Since every terminal has unit demand, $z'$ decomposes into one path per terminal. Then $y=dz'$ is unsplittable and

Thus an example based on equal binary commodities cannot work in a genuine graph. More generally, divisibility-chain demands are already a known positive case.

Costs must be genuinely distributed over the fractional support

The expected cost of independent path sampling from any terminal-wise path decomposition of $x$ is exactly $c^{\mathsf T}x$. Hence there is always at least one support routing of cost at most $c^{\mathsf T}x$.

Separately, DGG guarantees at least one support routing satisfying the load bounds. A counterexample must force these two nonempty families to be disjoint:

So neither a pure high-cost bypass construction nor a pure capacity gadget suffices.

The graph must go beyond the known positive structures

Any counterexample must lie outside the series-parallel class, where the required convex decomposition is now proved. arXiv Nonplanarity itself is not the established boundary: the supplied planar result gives the cost guarantee with $2D$, not a proof or disproof at $D$.

Dinitz_Garg_Goemans

The smallest credible topology therefore appears to require several interacting merge-split gadgets—a splice-closed “braid”—together with at least three genuinely incomparable demands and positive costs on support arcs.

5. Computational outcome of this attempt

I implemented two exact tests:

1. Full enumeration of all source-terminal paths and all unsplittable routings, followed by (SEP).

2. For larger path systems, column generation in which the pricing oracle is a binary min-cost unsplittable-flow program subject to $y\le x+D$.

In this session I screened:

• 7,248 small layered instances with three or four terminals and rational unequal demands;

• 378 larger random support-DAG instances using the integer pricing oracle;

• the cube/Figure-1 family and its seven-resource unique-good-selection refinement;

• small Wheatstone, complete layered, and repeated merge-split networks.

None produced a strictly positive separation value. This is not evidence sufficient to prove the conjecture, but it rules out the most direct clause, hypercube, zero-support-cost, and small-braid constructions.

Bottom line

The seven-resource construction is a sharp abstract counterexample, but path-splicing prevents it from being an SSUF counterexample. I found no valid graph instance with a positive separation certificate. The honest mathematical outcome is therefore a structured no-go result and an exact certification framework—not a disproof of Goemans’ conjecture. A genuine breakthrough must supply explicit rational $G,d,x,c$ together with $\operatorname{opt}(\mathrm{SEP})>0$; without that universal separation certificate, the proposed gadget has not defeated its hybrid paths.

Status after the extended search

I have not found a complete unconditional counterexample. Every construction that initially appeared to separate the cost condition acquired an additional unsplittable routing once all source–terminal paths were taken into account. Exact separation then returned value $0$.

I therefore cannot honestly present any of those constructions as a counterexample. The target statement is exactly the requirement that one unsplittable routing simultaneously satisfy

and

Dinitz_Garg_Goemans

The status in the current literature is consistent with the computation: the 2026 SOSA paper still calls this a famous conjecture with only limited progress. SIAM It has now been proved for series-parallel digraphs, so a counterexample—should one exist—must be outside that class. arXiv

What was tested exactly

For a fixed instance $(G,d,x)$, I used the exact separation program

A value $\delta>0$ would be an unconditional counterexample certificate. For larger graphs, the constraints were generated using an exact mixed-integer pricing problem: given $c$, it finds the minimum-cost unsplittable routing satisfying $y\le x+d_{\max}$. Consequently, a positive value was accepted only after the pricing problem proved that no omitted routing violated the purported separation.

The Figure 1 construction

I reconstructed the paper’s cube construction as an actual directed graph, retaining distinct parallel connector arcs. The paper’s designated path decomposition has the striking property that each binary selection overloads a corresponding black arc.

Dinitz_Garg_Goemans

But the graph contains many additional paths:

• 38 arcs;

• 162 support paths for each of the three terminals;

• 442,368 capacity-good routings at the symmetric fractional point.

After including these hybrid routings, the exact separation value was

Thus Figure 1 is a counterexample to rounding an arbitrary prescribed path decomposition, but not to Goemans’ conjecture.

Higher-dimensional cube gadgets

I tested the natural four- and five-terminal generalizations, with unequal demands and highly asymmetric fractional probabilities.

These produced especially convincing false positives. For example, in one five-terminal instance, a restricted separation LP returned approximately

After exact pricing generated all relevant hybrid routings, 621 routing columns were required and the value became

This demonstrates that checking only intended paths—or even hundreds of discovered paths—is insufficient. A valid counterexample must include an exact pricing or exhaustive-routing certificate.

Other tested families

The same zero-separation outcome occurred for:

• random orderings and repetitions of cube resources;

• binary and ternary finite-state track gadgets;

• sparse and dense layered nonplanar DAGs;

• assignment and row–cell networks;

• Wheatstone-type and repeated merge–split networks;

• random support DAGs with up to six terminals and six fractional support paths per terminal;

• unequal and mutually nondivisible demand vectors;

• extreme fractional probabilities close to $0$ and $1$.

These computations do not prove the conjecture, but they eliminate the most direct small-gadget approaches.

A new structured almost-counterexample—and its exact failure

The simplest new abstract construction uses two terminals. Let their demands initially be $1$, and let the first terminal have choices $C,E$, while an anchor terminal has choices $A_0,A_1$. Introduce two resources

Choose

with $0<\varepsilon<1/2$. Both resource loads in the fractional solution are

If $C$ and $A_j$ are selected, their integral load is $2$, and

Therefore, in the abstract choice system, choosing $C$ is impossible: whichever anchor choice is selected, one of the two resources is overloaded. Assign zero cost to $C,A_0,A_1$ and positive cost to $E$. All capacity-good abstract selections then choose $E$, whose cost is strictly larger than the fractional cost $(1-\varepsilon)c(E)$.

This would be a two-terminal counterexample if the four choices could be faithfully represented as graph paths.

They cannot. Suppose $e_0$ occurs before $e_1$. In the graph, the first terminal can:

1. start along the anchor track $A_1$;

2. enter the shared arc $e_1$;

3. leave $e_1$ along the suffix of $C$;

4. terminate at the first terminal.

This hybrid path uses $e_1$, but not $e_0$. The anchor can simultaneously choose $A_0$, which uses $e_0$, but not $e_1$. Each resource then receives load $1$, so

The routing is capacity-good and avoids the costly $E$ path. Reversing the order of $e_0,e_1$ merely reverses the hybrid.

This identifies a second fundamental obstruction, in addition to ordinary suffix splicing:

Because every commodity has the same source, a commodity may borrow the prefix of another commodity’s designated path and switch into its own path later.

Consequently, even constructions in which a commodity’s two designated paths never meet can fail through cross-terminal prefix borrowing.

Necessary properties now established for a genuine counterexample

A valid construction must simultaneously overcome all of the following.

1. It must be non-series-parallel. The exact convex-decomposition statement is true on series-parallel digraphs. arXiv

2. It must use genuinely unequal demands. For equal demands, integral min-cost flow yields the desired routing.

3. It cannot penalize only off-support arcs. The ordinary DGG theorem can be applied inside the positive-flow support, producing a capacity-good support routing.

4. It must survive suffix splicing. Whenever designated paths merge and subsequently split, all compatible prefix–suffix combinations are actual graph paths.

5. It must survive source-prefix borrowing. Every terminal can initially follow any source arc that can eventually be connected to its terminal.

6. Its cost obstruction must remain after complete path closure. Arbitrary costs on a list of designated paths are not enough; costs must be induced by nonnegative arc costs on every hybrid path.

7. It needs a strictly positive exact separation margin. Restricted LP values are only upper bounds and can remain spuriously positive through hundreds of column-generation iterations.

Strongest defensible conclusion

No unconditional counterexample has emerged. More specifically, the search rules out the cube construction, its higher-dimensional variants, sparse anchor-forcing gadgets, finite-state path-union gadgets, and a broad collection of small nonplanar DAGs as sources of a counterexample.

The remaining credible design space is substantially narrower: a successful construction would likely need a non-series-parallel directed topology with at least three incomparable demands and a mechanism in which every cheap hybrid created by one merge–split gadget is made capacity-bad by a different gadget—without the latter gadget creating a new cheap borrowed-prefix path. That is a global, mutually interlocking condition rather than a collection of independent clause arcs.

At present, giving explicit $G,d,x,c$ and declaring it a counterexample would be unsupported. The required final certificate remains a rational instance for which program (1) has a rigorously verified value $\delta>0$; none of the tested instances has that property.

Research update

I continued the search, but I do not yet have a positive, exact separation certificate, so there is still no unconditional counterexample to report. The conjecture remains open in the current literature. Its exact requirement is an unsplittable load $y$ satisfying

Dinitz_Garg_Goemans

Recent work still describes the cost conjecture as open with only limited progress. arXiv+1

The search strategy has, however, changed substantially. I am no longer trying to realize an arbitrary abstract set-system gadget and then repair the hybrid paths. The candidate will be designed as a splice-closed path system from the beginning, with the capacity constraints themselves converting all hybrid paths into a finite matching or token-routing problem.

1. The exact geometric target

For a fixed fractional flow $x$, define

On an acyclic graph, a counterexample exists precisely when

The uploaded paper also identifies convex decomposition as the formulation equivalent to the cost conjecture.

Dinitz_Garg_Goemans

There is one technical point worth making explicit. Ordinary separation of $x$ from $\operatorname{conv}\mathcal U(x)$ initially gives an arbitrary linear vector $p$, possibly with negative coordinates. This can always be converted into nonnegative arc costs.

For an arc $a=(u,v)$, choose vertex potentials $\pi$ such that

Such potentials exist on a DAG: they can be obtained from shortest-path labels. Then

All fractional and unsplittable flows under consideration have the same divergence vector, so

Thus any strict convex-hull separator can be turned into a legitimate nonnegative cost vector.

This means the search should focus entirely on (1). Costs are recovered automatically from the dual certificate.

2. The exchange structure explains the previous failures

Suppose paths of terminals $i$ and $j$ meet at a vertex $v$:

where $A_i,A_j$ are source–$v$ prefixes. The graph automatically contains the prefix-swapped paths

The cost change obtained by swapping both prefixes is

Equation (2) explains several phenomena.

When $d_i=d_j$, every such two-terminal exchange preserves total cost. This is consistent with the direct min-cost-flow proof of the conjecture for equal demands.

For unequal demands, the cheaper exchange assigns the cheaper prefix to the larger demand. Consequently, local merge–split gadgets impose a sorting structure. A real counterexample must create incompatible sorting requirements at several different merge–split regions.

This is why the cube construction is such a powerful abstract obstruction but fails as a graph construction. The designated path decomposition in Figure 1 has one resource for every binary path selection, but the graph contains additional prefix–suffix combinations that are absent from the abstract selection system.

Dinitz_Garg_Goemans

The correct target is therefore not a collection of paths. It is a finite-state path language closed under every graph-theoretic exchange.

3. Two new no-go results

3.1 Two-backbone prefix networks cannot give a counterexample

Consider the family consisting of two ordered backbone chains. Terminal $j$ may leave from either chain at position $j$. Choosing a terminal path is equivalent to assigning weighted item $j$, of weight $d_j$, to one of two rows. The backbone loads are weighted prefix sums.

Liu and Reis recently proved a weighted-chairman discrepancy bound

For $m=2$, this is $D/2$. arXiv+1

Combining this with the face-preserving cost-conversion theorem of Swamy, Traub, Vargas Koch, and Zenklusen gives the following deduction, which I have not found stated explicitly:

Two-backbone deduction. Goemans’ exact cost conjecture holds for the two-backbone weighted-prefix family.

Here is the argument. Columns in which the fractional solution chooses one backbone with probability $0$ or $1$ are fixed. Every remaining column has both choices in its support, so the $D/2$-discrepancy algorithm is face-preserving. Its error body $R$ has weighted-prefix width $D/2$. The cost conversion returns a no-more-expensive assignment in

whose prefix deviation is at most $D$. Connector-arc deviations are automatically at most $d_j\le D$. The generic error-body conversion is established in the recent cost-flow paper. arXiv

Thus the first plausible prefix-type construction needs at least three interacting backbones.

3.2 Three tracks cannot enforce a permutation

A more important obstruction emerged from the new token-routing approach.

Suppose three demands

must each traverse exactly one of three parallel gate arcs. Let their fractional gate loads be $x_1,x_2,x_3$, so

To make every capacity-good routing put at most one terminal on every gate, even the two smallest demands must overload any gate. Therefore we would need

Summing these inequalities yields

Since $D=d_1$, this is

which is impossible because $d_2,d_3\le D$.

Therefore:

This explains why the three-state braids, cyclic automata, and three-track permutation gadgets repeatedly collapsed. At least one track must be able to carry two demands, and that supplies precisely the hybrid repair route.

4. The first structurally credible candidate: three tokens and one hole

The preceding inequality changes as soon as there are four gates for three demands.

Take the rational demand vector

Its total demand is

Split the fractional load uniformly over four gate arcs:

Then

whereas the two smallest demands have sum

Consequently,

for every pair of terminals and every gate. Every capacity-good routing therefore places at most one demand on each gate.

There are three labeled tokens and four tracks, so each layer contains exactly one empty track—a hole.

This is the first candidate architecture in which the capacity bound itself neutralizes path splicing:

• Every individual terminal may follow any hybrid path.

• Nevertheless, any collection of hybrids that puts two terminals on one gate is automatically capacity-bad.

• Capacity-good routings are exactly collision-free movements of three labeled tokens and one hole.

This bypasses the fatal weakness of the cube gadget. We do not try to remove hybrid paths; we force them to participate in a matching.

The hole-braid graph

Use four states at every layer. Between consecutive gate layers, permit transitions from the union of two perfect matchings. Suitable initial layers are generated by permutations such as

At layer $\ell$, a token on track $i$ may remain on $i$ or move to $\sigma_\ell(i)$. Gate arcs are inserted before or after every transition layer.

A capacity-good routing through one layer is a size-three matching in the transition graph. Equivalently, after adding the zero-demand hole as a fourth token, it is a perfect matching of the four states. A multilayer routing becomes a path in a finite configuration graph on at most

states.

Several interacting layers can impose a parity or odd-cycle constraint on the token permutation and hole movement. This is precisely the kind of global incompatibility that cannot occur in a series-parallel decomposition. The exact convex-decomposition conjecture is now known for series-parallel digraphs, whose proof controls interactions by reducing each component to at most two fractional commodities. arXiv The hole braid deliberately creates a component with three simultaneously interacting unequal demands.

5. The exact search is now a configuration-polytope calculation

The new construction permits a much stronger test than enumerating arbitrary source-terminal paths.

Let $\Omega_\ell$ be the set of collision-free configurations at layer $\ell$. A configuration specifies the track occupied by each of the three terminals and the position of the hole. Introduce a variable

for every allowed transition from configuration $\omega\in\Omega_\ell$ to configuration $\omega'\in\Omega_{\ell+1}$.

These variables satisfy ordinary flow-conservation equations in the configuration DAG:

For every original graph arc $a$, impose the marginal equation

where $L_a(\omega,\omega')$ is the total demand using $a$ in that configuration transition.

The feasibility of (3) is exactly the test

This formulation has three major advantages.

First, it includes every hybrid path automatically. Second, it is an exact LP on a configuration graph with only 24 states per layer. Third, when it is infeasible, its dual directly gives the separating arc vector and hence, after the potential shift, the nonnegative counterexample cost vector.

The remaining search is therefore:

1. Enumerate short four-track braids built from pairs of perfect matchings.

2. Construct a symmetric rational fractional flow with gate load $11/16$.

3. Solve configuration-polytope membership exactly.

4. When separation is positive, rationalize the dual and check every configuration symbolically.

5. Convert the separator to nonnegative arc costs using DAG potentials.

This is substantially stronger than randomized graph enumeration. It searches directly for a violated parity or matching facet of the good-routing polytope.

6. Results of the first probes

The structured lower-bound instances from the weighted-chairman paper do not themselves yield cost counterexamples. I tested its three-row support-preserving construction at

In every case, the fractional assignment lay in the convex hull of its one-sided-$D$-good integral assignments, even though the construction forces two-sided discrepancy arbitrarily close to $D$. This is an important distinction:

Large discrepancy does not imply a cost counterexample. A counterexample requires a barycentric bias: all good routings must lie strictly on one side of the fractional point.

For the four-track hole family, the completed exact tests give:

• one transition layer, eight paths per terminal and 512 total routings: separation $0$ for the symmetric point and for the tested sparse and perturbed fractional flows;

• the symmetric point of the first two-layer cyclic template: separation $0$.

This says that a single matching layer is too shallow. It behaves like an assignment-rounding instance. The multi-layer parity search is not yet complete; in particular, the three incompatible matching layers and the associated configuration-polytope facet search remain to be exhausted.

Present conclusion

The counterexample search is now concentrated on a sharply defined minimal frontier:

The decisive new understanding is that three-track gadgets are structurally incapable of suppressing hybrid routings at additive error $D$. Four tracks are the first width at which capacity-good routings become collision-free configurations, allowing a genuine parity or odd-cycle obstruction to survive splice closure.

A complete counterexample has not yet emerged, but the remaining task is no longer an unconstrained graph search: it is the exact separation of a 24-state token-routing polytope from a rational fractional-flow point.