Diffusion-Robust Optimization over Graphs
This work provides insights into the computational landscape of robust graph optimization under a topology-aware uncertainty model, which is relevant for researchers and practitioners in networked systems like transportation and logistics.
This paper introduces a diffusion-based uncertainty model for robust optimization on directed graphs, where edge weight perturbations propagate along adjacent edges. For convex network problems like minimum-cost flow, the robust formulations remain convex and polynomial-time solvable. For shortest path, tractability depends sharply on propagation depth, while for TSP, robustness often adds no computational complexity.
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. For convex network problems, such as minimum-cost flow and maximum flow, the resulting formulations remain convex and admit polynomial-time solution methods across all diffusion regimes considered. For combinatorial problems, the effect is more delicate. 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.