{"ID":2861721,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.02562","arxiv_id":"2510.02562","title":"Near-Optimal Fault-Tolerant Strong Connectivity Preservers","abstract":"A $k$-fault-tolerant connectivity preserver of a directed $n$-vertex graph $G$ is a subgraph $H$ such that, for any edge set $F \\subseteq E(G)$ of size $|F| \\le k$, the strongly connected components of $G - F$ and $H - F$ are the same. While some graphs require a preserver with $Ω(2^{k}n)$ edges [BCR18], the best-known upper bound is $\\tilde{O}(k2^{k}n^{2-1/k})$ edges [CC20], leaving a significant gap of $Ω(n^{1-1/k})$. In contrast, there is no gap in undirected graphs; the optimal bound of $Θ(kn)$ has been well-established since the 90s [NI92]. We nearly close the gap for directed graphs; we prove that there exists a $k$-fault-tolerant connectivity preserver with $O(k4^{k}n\\log n)$ edges, and we can construct one with $O(8^{k}n\\log^{5/2}n)$ edges in $\\text{poly}(2^{k}n)$ time. Our results also improve the state-of-the-art for a closely related object; a \\textit{$k$-connectivity preserver} of $G$ is a subgraph $H$ where, for all $i \\le k$, the strongly $i$-connected components of $G$ and $H$ agree. By a known reduction, we obtain a $k$-connectivity preserver with $O(k4^{k}n\\log n)$ edges, improving the previous best bound of $\\tilde{O}(k2^{k}n^{2-1/(k-1)})$ [CC20]. Therefore, for any constant $k$, our results are optimal to a $\\log n$ factor for both problems. Lastly, we show that the exponential dependency on $k$ is not inherent for $k$-connectivity preservers by presenting another construction with $O(n \\sqrt{kn})$ edges.","short_abstract":"A $k$-fault-tolerant connectivity preserver of a directed $n$-vertex graph $G$ is a subgraph $H$ such that, for any edge set $F \\subseteq E(G)$ of size $|F| \\le k$, the strongly connected components of $G - F$ and $H - F$ are the same. While some graphs require a preserver with $Ω(2^{k}n)$ edges [BCR18], the best-known...","url_abs":"https://arxiv.org/abs/2510.02562","url_pdf":"https://arxiv.org/pdf/2510.02562v1","authors":"[\"Gary Hoppenworth\",\"Thatchaphol Saranurak\",\"Benyu Wang\"]","published":"2025-10-02T20:58:41Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}