pith. sign in

arxiv: 2605.30853 · v2 · pith:QT7GKOP2new · submitted 2026-05-29 · 🧮 math.OC · cs.CC· cs.DM· math.CO

Diffusion-Robust Optimization over Graphs

Liviu Aolaritei , Ricky Huang , Michael I. Jordan , Paul Grigas This is my paper

Pith reviewed 2026-06-28 21:47 UTC · model grok-4.3

classification 🧮 math.OC cs.CCcs.DMmath.CO
keywords robust optimizationgraph optimizationshortest pathtraveling salesman problemdiffusion uncertaintycombinatorial optimizationnetworked systems
0
0 comments X

The pith

Diffusion uncertainty on graphs makes robust shortest path tractability depend on propagation depth while TSP complexity stays the same.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a diffusion-based uncertainty model for robust optimization on directed graphs, where perturbations propagate along edges while obeying node conservation. It examines the effects on two problems: shortest path, which is easy without robustness, and TSP, which is hard. The analysis reveals that increasing the depth of diffusion causes a sharp change from solvable to unsolvable robust shortest path versions. For TSP, the robust version does not increase difficulty because the adversarial problem on a fixed tour reduces to simple formulas. This matters for designing robust solutions in networks like transportation where uncertainty spreads locally.

Core claim

For shortest path, propagation depth induces a sharp transition between tractable and intractable robust counterparts. For the traveling salesman problem, robustness often adds no computational complexity beyond ordinary TSP, because the structure of Hamiltonian cycles makes the fixed-tour adversarial problem collapse to explicit formulas.

What carries the argument

The diffusion-based uncertainty model in which perturbations of edge weights propagate along adjacent edges and satisfy conservation constraints at nodes.

If this is right

  • For shortest path problems, there exists a critical propagation depth beyond which the robust counterpart becomes computationally intractable.
  • The traveling salesman problem under this uncertainty model has the same computational complexity as the nominal version due to explicit formulas for the adversarial cost.
  • Tractability in robust graph optimization is governed by the interaction between propagation depth, budget geometry, and the structure of feasible solutions.
  • The topology-aware uncertainty fundamentally alters the computational landscape compared to standard robust optimization.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This model could be extended to other combinatorial problems on graphs such as minimum spanning tree or network flow to see similar transitions.
  • Practitioners in logistics might use low-depth diffusion models to keep robust shortest path computations efficient.
  • Further research could identify the exact threshold depth where the transition occurs for specific graph classes.

Load-bearing premise

The diffusion-based uncertainty model with propagation along edges and conservation constraints at nodes accurately captures the relevant uncertainty structure in the target networked systems.

What would settle it

Solve the robust shortest path for increasing propagation depths on a small directed graph and check if there is a point where it switches from polynomial to NP-hard.

Figures

Figures reproduced from arXiv: 2605.30853 by Liviu Aolaritei, Michael I. Jordan, Paul Grigas, Ricky Huang.

Figure 1
Figure 1. Figure 1: Local diffusion effect at a path node 𝑢. The gray edges 𝑒 in 𝑢 and 𝑒 out 𝑢 are the edges used by the path to enter and leave 𝑢. The red edges indicate other incoming edges of 𝑢. Under short-term diffusion, perturbation mass available at the incoming edges of 𝑢 may be transferred through 𝑢 and used to worsen the next step 𝑒 out 𝑢 . However, the amount that can leave any edge is bounded solely by its nominal… view at source ↗
Figure 2
Figure 2. Figure 2: Construction of 𝐺′ = (𝑉 ′ , 𝐸′ ) from 𝐺 = (𝑉, 𝐸). Top: each node 𝑣 ∈ 𝑉 is replaced by an edge-chain gadget 𝐸𝑣, together with a dummy edge 𝛼𝑣 = (𝑑𝑣, 𝑐𝑣) of nominal weight 1 and a zero-weight entry edge 𝛽𝑣 = (𝑐𝑣, 𝑣1). Middle: each original arc (𝑢, 𝑣) ∈ 𝐸 induces an anchor edge 𝑎𝑢,𝑣 (solid blue). Bottom: each closed out-neighborhood relation 𝑣 ∈ 𝑁[𝑢] ∖ {𝑢} induces a connector edge 𝑐𝑣,𝑢 (dashed blue). All othe… view at source ↗
Figure 3
Figure 3. Figure 3: Example illustrating the reduction from Most Secluded Path to Diff-RSP under [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Construction of 𝐺′′ = (𝑉 ′′, 𝐸′′) from 𝐺 = (𝑉, 𝐸). Top: each node 𝑣 ∈ 𝑉 is replaced by a chain gadget 𝐸𝑣 of length 4|𝑉 |, together with a dummy edge 𝛼𝑣 = (𝑑𝑣, 𝑐𝑣) of nominal weight 1 and an entry edge 𝛽𝑣 = (𝑐𝑣, 𝑣1). Middle: each original arc (𝑢, 𝑣) ∈ 𝐸 induces an anchor edge 𝑎𝑢,𝑣 from the end of 𝐸𝑢 to the beginning of 𝐸𝑣 (solid blue). Bottom: each relation 𝑣 ∈ 𝑁[𝑢] ∖ {𝑢} induces a connector edge 𝑐𝑣,𝑢 = (𝑐𝑣… view at source ↗
Figure 5
Figure 5. Figure 5: Example illustrating the reduction from Most Secluded Path to Diff-RSP under [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Visualization of the graph in Example [PITH_FULL_IMAGE:figures/full_fig_p022_6.png] view at source ↗
read the original abstract

We introduce a diffusion-based uncertainty model for robust optimization on directed graphs, in which perturbations of edge weights propagate along adjacent edges and satisfy conservation constraints at nodes. This topology-aware structure is natural in networked systems where uncertainty is induced by flows and local interactions, including transportation, logistics, communication, and energy networks. We analyze how such diffusive uncertainty reshapes the computational landscape of robust graph optimization. We focus on two canonical combinatorial graph problems, shortest path and the traveling salesman problem (TSP), which provide complementary benchmarks: shortest path is polynomial-time solvable in the nominal setting, whereas TSP is already NP-hard. We show that, for shortest path, propagation depth induces a sharp transition between tractable and intractable robust counterparts. For the traveling salesman problem, robustness often adds no computational complexity beyond ordinary TSP, because the structure of Hamiltonian cycles makes the fixed-tour adversarial problem collapse to explicit formulas. Together, these results show that topology-aware uncertainty can fundamentally change robust combinatorial optimization, with tractability governed by the interaction between propagation, budget geometry, and the structure of feasible solutions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper introduces a diffusion-based uncertainty model for robust optimization on directed graphs, where edge-weight perturbations propagate along adjacent edges subject to conservation constraints at nodes. It analyzes the resulting robust counterparts of two canonical problems: for shortest paths, propagation depth induces a sharp tractability transition; for TSP, the fixed-tour adversarial subproblem collapses to explicit formulas, so that robustness adds no computational complexity beyond ordinary TSP.

Significance. If the claimed sharp transition and complexity equivalence hold, the work would be significant for robust combinatorial optimization on networks. It demonstrates that the interaction between uncertainty geometry (propagation depth and budget) and feasible-set structure can qualitatively alter tractability, offering a topology-aware alternative to standard budgeted or ellipsoidal uncertainty sets. The modeling choice is presented as a deliberate modeling decision rather than a fitted parameter.

minor comments (2)
  1. The abstract states that robustness 'often adds no computational complexity' for TSP; the precise conditions (e.g., which budgets or propagation depths) under which the collapse to explicit formulas occurs should be stated explicitly in the introduction or main theorem statement.
  2. The diffusion model is introduced as a modeling choice; a short paragraph contrasting it with standard budgeted or polyhedral uncertainty sets would help readers situate the contribution.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our work on diffusion-robust optimization over graphs and for recommending minor revision. The referee summary accurately captures the core contributions regarding the diffusion-based uncertainty model, the tractability transition for shortest paths, and the complexity equivalence for TSP. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper introduces a new diffusion-based uncertainty model defined via propagation along edges and node conservation constraints, then derives complexity results for shortest-path and TSP by analyzing how this model interacts with the feasible sets of each problem. The tractability transition for shortest path is tied to propagation depth, and the TSP claim rests on the explicit collapse of the adversarial subproblem for fixed tours; neither reduces by construction to fitted parameters, self-definitions, or prior self-citations. The modeling premise is stated as an explicit choice whose consequences are then examined mathematically, rendering the derivation chain self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 1 invented entities

The central claims rest on the newly introduced diffusion uncertainty model and standard graph-theoretic assumptions; limited detail available from abstract.

free parameters (1)
  • propagation depth
    Controls how far perturbations spread and is central to the claimed tractability transition for shortest path.
axioms (1)
  • domain assumption Perturbations of edge weights propagate along adjacent edges and satisfy conservation constraints at nodes
    Core modeling choice stated in the abstract for the uncertainty structure.
invented entities (1)
  • diffusion-based uncertainty model no independent evidence
    purpose: To represent topology-aware perturbations that propagate with conservation in networked systems
    Newly postulated model introduced to capture flow-induced uncertainty.

pith-pipeline@v0.9.1-grok · 5722 in / 1233 out tokens · 25270 ms · 2026-06-28T21:47:43.647770+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

62 extracted references · 1 linked inside Pith

  1. [1]

    R. K. Ahuja, T. L. Magnanti, and J. B. Orlin.Network flows. Cambridge, Mass.: Alfred P. Sloan School of Management, Massachusetts, 1988. 23

    1988

  2. [2]

    Min–maxandmin–maxregretversionsofcombinatorial optimizationproblems: Asurvey.European Journal of Operational Research, 197(2):427–438, 2009

    H.Aissi, C.Bazgan, andD.Vanderpooten. Min–maxandmin–maxregretversionsofcombinatorial optimizationproblems: Asurvey.European Journal of Operational Research, 197(2):427–438, 2009

    2009

  3. [3]

    Alves Pessoa, L

    A. Alves Pessoa, L. Di Puglia Pugliese, F. Guerriero, and M. Poss. Robust constrained shortest path problems under budgeted uncertainty.Networks, 66(2):98–111, 2015

    2015

  4. [4]

    Atamtürk and M

    A. Atamtürk and M. Zhang. Two-stage robust network flow and design under demand uncertainty. Operations research, 55(4):662–673, 2007

    2007

  5. [5]

    Averbakh and V

    I. Averbakh and V. Lebedev. Interval data minmax regret network optimization problems.Discrete Applied Mathematics, 138(3):289–301, 2004

    2004

  6. [6]

    Bartolini, D

    E. Bartolini, D. Goeke, M. Schneider, and M. Ye. The robust traveling salesman problem with time windows under knapsack-constrained travel time uncertainty.Transportation Science, 55(2): 371–394, 2021

    2021

  7. [7]

    Ben-Tal and A

    A. Ben-Tal and A. Nemirovski. Robust convex optimization.Mathematics of operations research, 23(4):769–805, 1998

    1998

  8. [8]

    Ben-Tal and A

    A. Ben-Tal and A. Nemirovski. Robust solutions of uncertain linear programs.Operations Research Letters, 25(1):1–13, 1999

    1999

  9. [9]

    Ben-Tal, A

    A. Ben-Tal, A. Nemirovski, and L. El Ghaoui.Robust Optimization. Princeton university press, 2009

    2009

  10. [10]

    D. P. Bertsekas. Robust shortest path planning and semicontractive dynamic programming.Naval Research Logistics (NRL), 66(1):15–37, 2019

    2019

  11. [11]

    Bertsimas and M

    D. Bertsimas and M. Sim. Robust discrete optimization and network flows.Mathematical Pro- gramming, 98(1):49–71, 2003

    2003

  12. [12]

    Bertsimas, D

    D. Bertsimas, D. B. Brown, and C. Caramanis. Theory and applications of robust optimization. SIAM review, 53(3):464–501, 2011

    2011

  13. [13]

    Bertsimas, E

    D. Bertsimas, E. Nasrabadi, and S. Stiller. Robust and adaptive network flows.Operations Research, 61(5):1218–1242, 2013

    2013

  14. [14]

    M. E. Bruni and F. Guerriero. An enhanced exact procedure for the absolute robust shortest path problem.International Transactions in Operational Research, 17(2):207–220, 2010

    2010

  15. [15]

    C. Büsing. Recoverable robust shortest path problems.Networks, 59(1):181–189, 2012

    2012

  16. [16]

    J. G. Carlsson, M. Behroozi, and K. Mihic. Wasserstein distance and the distributionally robust TSP.Operations Research, 66(6):1603–1624, 2018

    2018

  17. [17]

    Catanzaro, M

    D. Catanzaro, M. Labbe, and M. Salazar-Neumann. Reduction approaches for robust shortest path problems.Computers & Operations Research, 38(11):1610–1619, 2011

    2011

  18. [18]

    Chassein and M

    A. Chassein and M. Goerigk. On the recoverable robust traveling salesman problem.Optimization Letters, 10(7):1479–1492, 2016. 24

    2016

  19. [19]

    Chassein, T

    A. Chassein, T. Dokka, and M. Goerigk. Algorithms and uncertainty sets for data-driven robust shortest path problems.European Journal of Operational Research, 274(2):671–686, 2019

    2019

  20. [20]

    Chechik, M

    S. Chechik, M. P. Johnson, M. Parter, and D. Peleg. Secluded connectivity problems.Algorithmica, 79(3):708–741, 2017

    2017

  21. [21]

    Cheng, A

    J. Cheng, A. Lisser, and M. Letournel. Distributionally robust stochastic shortest path problem. Electronic Notes in Discrete Mathematics, 41:511–518, 2013

    2013

  22. [22]

    Cheng, J

    J. Cheng, J. Leung, and A. Lisser. New reformulations of distributionally robust shortest path problem.Computers & Operations Research, 74:196–204, 2016

    2016

  23. [23]

    Di Puglia Pugliese, F

    L. Di Puglia Pugliese, F. Guerriero, and M. Poss. The resource constrained shortest path prob- lem with uncertain data: A robust formulation and optimal solution approach.Computers & Operations Research, 107:140–155, 2019

    2019

  24. [24]

    Duque and A

    D. Duque and A. L. Medaglia. An exact method for a class of robust shortest path problems with scenarios.Networks, 74(4):360–373, 2019

    2019

  25. [25]

    Filippi, F

    C. Filippi, F. Maggioni, and M. G. Speranza. Robust and distributionally robust shortest path problems: A survey.Computers & Operations Research, 182:107096, 2025

    2025

  26. [26]

    Gabrel, C

    V. Gabrel, C. Murat, and A. Thiele. Recent advances in robust optimization: An overview. European Journal of Operational Research, 235(3):471–483, 2014

    2014

  27. [27]

    Ganesh, B

    A. Ganesh, B. M. Maggs, and D. Panigrahi. Robust algorithms for TSP and Steiner tree.ACM Transactions on Algorithms, 19(2):1–37, 2023

    2023

  28. [28]

    Ghosal and W

    S. Ghosal and W. Wiesemann. The distributionally robust chance-constrained vehicle routing problem.Operations Research, 68(3):716–732, 2020

    2020

  29. [29]

    Goerigk and M

    M. Goerigk and M. Hartisch. An introduction to robust combinatorial optimization.International Series in Operations Research and Management Science, 2024

    2024

  30. [30]

    Goerigk and M

    M. Goerigk and M. Khosravi. Benchmarking problems for robust discrete optimization.Computers & Operations Research, 166:106608, 2024

    2024

  31. [31]

    Goerigk, S

    M. Goerigk, S. Lendl, and L. Wulf. On the recoverable traveling salesman problem.arXiv preprint arXiv:2111.09691, 2021

    arXiv 2021

  32. [32]

    Golovin, V

    D. Golovin, V. Goyal, V. Polishchuk, R. Ravi, and M. Sysikaski. Improved approximations for two-stage min-cut and shortest path problems under uncertainty.Mathematical Programming, 149 (1):167–194, 2015

    2015

  33. [33]

    C. E. Gounaris, W. Wiesemann, and C. A. Floudas. The robust capacitated vehicle routing problem under demand uncertainty.Operations Research, 61(3):677–693, 2013

    2013

  34. [34]

    Hansknecht, A

    C. Hansknecht, A. Richter, and S. Stiller. Fast robust shortest path computations. In18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018), pages 5–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018. 25

    2018

  35. [35]

    C. Hu, J. Lu, X. Liu, and G. Zhang. Robust vehicle routing problem with hard time windows under demand and travel time uncertainty.Computers & Operations Research, 94:139–153, 2018

    2018

  36. [36]

    Jackiewicz, A

    M. Jackiewicz, A. Kasperski, and P. Zieliński. Computational complexity of the recoverable robust shortest path problem with discrete recourse.Discrete Applied Mathematics, 370:103–110, 2025

    2025

  37. [37]

    O. E. Karaşan, M. C. Pınar, and H. Yaman. The robust shortest path problem with interval data. Technical report, Bilkent University, Department of Industrial Engineering, Ankara, Turkey, 2001. Technical report

    2001

  38. [38]

    Kasperski and P

    A. Kasperski and P. Zieliński. The robust shortest path problem in series–parallel multidigraphs with interval data.Operations Research Letters, 34(1):69–76, 2006

    2006

  39. [39]

    Kasperski and P

    A. Kasperski and P. Zieliński. Robust discrete optimization under discrete and interval uncertainty: A survey. InRobustness Analysis in Decision Aiding, Optimization, and Analytics, pages 113–143. Springer, 2016

    2016

  40. [40]

    S. S. Ketkov. On the multistage shortest path problem under distributional uncertainty.Journal of Optimization Theory and Applications, 197(1):277–308, 2023

    2023

  41. [41]

    S. S. Ketkov, O. A. Prokopyev, and E. P. Burashnikov. An approach to the distributionally robust shortest path problem.Computers & Operations Research, 130:105212, 2021

    2021

  42. [42]

    Kouvelis and G

    P. Kouvelis and G. Yu.Robust Discrete Optimization and its Applications, volume 14. Springer Science & Business Media, 2013

    2013

  43. [43]

    C. Kwon, T. Lee, and P. Berglund. Robust shortest path problems with two uncertain multiplica- tive cost coefficients.Naval Research Logistics (NRL), 60(5):375–394, 2013

    2013

  44. [44]

    J.-Q. Li, N. Kong, X. Hu, and L. Liu. Large-scale transit itinerary planning under uncertainty. Transportation Research Part C: Emerging Technologies, 60:397–415, 2015

    2015

  45. [45]

    Liebchen, M

    C. Liebchen, M. Lübbecke, R. Möhring, and S. Stiller. The concept of recoverable robustness, linear programming recovery, and railway applications. InRobust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems, pages 1–27. Springer, 2009

    2009

  46. [46]

    Montemanni and L

    R. Montemanni and L. M. Gambardella. An exact algorithm for the robust shortest path problem with interval data.Computers & Operations Research, 31(10):1667–1680, 2004

    2004

  47. [47]

    Montemanni and L

    R. Montemanni and L. M. Gambardella. The robust shortest path problem with interval data via Benders decomposition.4or, 3(4):315–328, 2005

    2005

  48. [48]

    Montemanni, L

    R. Montemanni, L. M. Gambardella, and A. V. Donati. A branch and bound algorithm for the robust shortest path problem with interval data.Operations Research Letters, 32(3):225–232, 2004

    2004

  49. [49]

    Montemanni, J

    R. Montemanni, J. Barta, M. Mastrolilli, and L. M. Gambardella. The robust traveling salesman problem with interval data.Transportation Science, 41(3):366–381, 2007

    2007

  50. [50]

    Munari, A

    P. Munari, A. Moreno, J. De La Vega, D. Alem, J. Gondzio, and R. Morabito. The robust vehicle routing problem with time windows: Compact formulation and branch-price-and-cut method. Transportation Science, 53(4):1043–1066, 2019. 26

    2019

  51. [51]

    Murthy and S.-S

    I. Murthy and S.-S. Her. Solving min-max shortest-path problems on a network.Naval Research Logistics (NRL), 39(5):669–683, 1992

    1992

  52. [52]

    Nasrabadi and J

    E. Nasrabadi and J. B. Orlin. Robust optimization with incremental recourse.arXiv preprint arXiv:1312.4075, 2013

    Pith/arXiv arXiv 2013

  53. [53]

    F. Ordóñez. Robust vehicle routing. InRisk and Optimization in an Uncertain World, pages 153–178. INFORMS, 2010

    2010

  54. [54]

    C. H. Papadimitriou and K. Steiglitz.Combinatorial Optimization: Algorithms and Complexity. Courier Corporation, 1998

    1998

  55. [55]

    Raith, M

    A. Raith, M. Schmidt, A. Schöbel, and L. Thom. Extensions of labeling algorithms for multi- objective uncertain shortest path problems.Networks, 72(1):84–127, 2018

    2018

  56. [56]

    Şeref, R

    O. Şeref, R. K. Ahuja, and J. B. Orlin. Incremental network optimization: Theory and algorithms. Operations Research, 57(3):586–594, 2009

    2009

  57. [57]

    Shahabi, A

    M. Shahabi, A. Unnikrishnan, and S. D. Boyles. Robust optimization strategy for the shortest path problem under uncertain link travel cost distribution.Computer-Aided Civil and Infrastructure Engineering, 30(6):433–448, 2015

    2015

  58. [58]

    Z. Wang, K. You, S. Song, and Y. Zhang. Wasserstein distributionally robust shortest path problem.European Journal of Operational Research, 284(1):31–43, 2020

    2020

  59. [59]

    Xing and X

    T. Xing and X. Zhou. Reformulation and solution algorithms for absolute and percentile robust shortest path problems.IEEE Transactions on Intelligent Transportation Systems, 14(2):943–954, 2013

    2013

  60. [60]

    Xu and X

    B. Xu and X. Zhou. Dynamic relative robust shortest path problem.Computers & Industrial Engineering, 148:106651, 2020

    2020

  61. [61]

    Yu and J

    G. Yu and J. Yang. On the robust shortest path problem.Computers & Operations Research, 25 (6):457–468, 1998

    1998

  62. [62]

    Zieliński

    P. Zieliński. The computational complexity of the relative robust shortest path problem with interval data.European Journal of Operational Research, 158(3):570–576, 2004. A Proofs A.1 Proofs for Section 2 A.1.1 Proof of Theorem 2.1 Assertions (i) and (ii) follow from Proposition 2.2. Assertion (iii) follows from Proposition 2.5. Asser- tion (iv) follows f...

    2004