Strong Connectivity Oracle for Multiple Failures via Rooted Flow-Augmentation
In the authors' words
We present a significantly improved -fault-tolerant strong connectivity oracle, one of the most basic data structures on a directed graph that, given any set of failed edges of size , answers whether is strongly connected. For every constant , our oracle only uses space and query time. No prior result can achieve space and query time, even when . Previous oracles either require query time [BCR18], or space [vdBS19]. Our main technical contribution is a rooted version of the highly successful flow augmentation technique, which may be of independent interest. Given a directed graph , an integer , and a source vertex , we can sample a set of edges such that each minimal -rooted cut of size at most becomes an -rooted min-cut in with probability .
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: SODA 2027