On Explicit Constructions of Extremely Depth Robust Graphs

Jeremiah Blocki, Mike Cinkoske, Seunghoon Lee +1

A directed acyclic graph $G=(V,E)$ is said to be $(e,d)$-depth robust if for every subset $S\subseteq V$ of $|S|\le e$ nodes the graph $G-S$ still contains a directed path of le…