New Separations and Reductions for Directed Preservers and Hopsets

Gary Hoppenworth, Yinzhan Xu, Zixuan Xu

We study distance preservers, hopsets, and shortcut sets in $n$-node, $m$-edge directed graphs, and show improved bounds and new reductions for various settings of these problems.…