{"ID":2846506,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.01239","arxiv_id":"2511.01239","title":"Fault-Tolerant Approximate Distance Oracles with a Source Set","abstract":"Our input is an undirected weighted graph $G = (V,E)$ on $n$ vertices along with a source set $S\\subseteq V$. The problem is to preprocess $G$ and build a compact data structure such that upon query $Qu(s,v,f)$ where $(s,v) \\in S\\times V$ and $f$ is any faulty edge, we can quickly find a good estimate (i.e., within a small multiplicative stretch) of the $s$-$v$ distance in $G-f$. The work of Bil{ò} et al. (Algorithmica 2022) on multiple-edge fault-tolerant approximate shortest path trees implies a compact oracle for the above problem with a stretch of at most 3 and with query answering time $O(\\log^2 n)$. We show a very simple construction of an $S\\times V$ approximate distance oracle with $O(1)$ query answering time; its size is $\\widetilde{O}(|S|n + n^{3/2})$ and multiplicative stretch is at most 5. A single-edge fault-tolerant $ST$-distance oracle from the work of Bil{ò} et al. (STACS 2018) plays a key role in our construction. We also give a construction of a fault-tolerant $S \\times V$ approximate distance oracle of size $\\widetilde{O}(|S|n + n^{4/3})$ with multiplicative stretch at most 13 and as before, with $O(1)$ query answering time.","short_abstract":"Our input is an undirected weighted graph $G = (V,E)$ on $n$ vertices along with a source set $S\\subseteq V$. The problem is to preprocess $G$ and build a compact data structure such that upon query $Qu(s,v,f)$ where $(s,v) \\in S\\times V$ and $f$ is any faulty edge, we can quickly find a good estimate (i.e., within a s...","url_abs":"https://arxiv.org/abs/2511.01239","url_pdf":"https://arxiv.org/pdf/2511.01239v2","authors":"[\"Dipan Dey\",\"Telikepalli Kavitha\"]","published":"2025-11-03T05:26:26Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}