6 papers · 1 filter
Hardness of Online Directed Steiner Network
Gary Hoppenworth, Yaowei Long, Sepideh Mahabadi +1
In the Directed Steiner Network (DSN) problem we are given a directed graph and a set of demands , and asked to find a cheap subgraph connecting each terminal pair. In i…
Reviving Thorup's Shortcut Conjecture
Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg +7
We aim to revive Thorup's conjecture [Thorup, WG'92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph…
Near-Optimal Fault-Tolerant Strong Connectivity Preservers
Gary Hoppenworth, Thatchaphol Saranurak, Benyu Wang
A -fault-tolerant connectivity preserver of a directed -vertex graph is a subgraph such that, for any edge set of size , the strongly co…
Better Bounds for Semi-Streaming Single-Source Shortest Paths
Sepehr Assadi, Gary Hoppenworth, Janani Sundaresan
In the semi-streaming model, an algorithm must process any -vertex graph by making one or few passes over a stream of its edges, use words of space…
Covering Approximate Shortest Paths with DAGs
Sepehr Assadi, Gary Hoppenworth, Nicole Wein
We define and study analogs of probabilistic tree embedding and tree cover for directed graphs. We define the notion of a DAG cover of a general directed graph : a small collect…
New Separations and Reductions for Directed Preservers and Hopsets
Gary Hoppenworth, Yinzhan Xu, Zixuan Xu
We study distance preservers, hopsets, and shortcut sets in -node, -edge directed graphs, and show improved bounds and new reductions for various settings of these problems.…