Preprint
Sep 2026
Hardness of Online Directed Steiner Network
In the Directed Steiner Network (DSN) problem we are given a directed graph and a set of demands $(s_i,t_i)$, and asked to find a cheap subgraph connecting each terminal pair. In its online version, the demands arrive online and must be served by buying edges irrevocably. DSN is a fundamental hard problem in network de...
Gary Hoppenworth, Yao-Wei Long, S. Mahabadi et al.
· 0 citations