Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917879561060352 |
|---|---|
| author | Bilò, Davide Choudhary, Keerti Cohen, Sarel Friedrich, Tobias Schirneck, Martin |
| author_facet | Bilò, Davide Choudhary, Keerti Cohen, Sarel Friedrich, Tobias Schirneck, Martin |
| contents | We design sensitivity oracles for error-prone networks. For a network problem $Π$, the data structure preprocesses a network $G=(V,E)$ and sensitivity parameter $f$ such that, for any set $F\subseteq V\cup E$ of up to $f$ link or node failures, it can report a solution for $Π$ in $G{-}F$. We study three network problems $Π$. $L$-Hop Shortest Path: Given $s,t \in V$, is there a shortest $s$-$t$-path in $G-F$ with at most $L$ links? $k$-Path: Does $G-F$ contain a simple path with $k$ links? $k$-Clique: Does $G-F$ contain a clique of $k$ nodes? Our main technical contribution is a new construction of $(L,f)$-replacement path coverings ($(L,f)$-RPC) in the parameter realm where $f = o(\log L)$. An $(L,f)$-RPC is a family $\mathcal{G}$ of subnetworks of $G$ which, for every $F \subseteq E$ with $|F| \le f$, contain a subfamily $\mathcal{G}_F \subseteq \mathcal{G}$ such that (i) no subnetwork in $\mathcal{G}_F$ contains a link of $F$ and (ii) for each $s,t \in V$, if $G-F$ contains a shortest $s$-$t$-path with at most $L$ links, then some subnetwork in $\mathcal{G}_F$ retains at least one such path. Our $(L, f)$-RPC has almost the same size as the one by Weimann and Yuster [ACM TALG 2013] but it improves the time to query $\mathcal{G}_F$ from $\widetilde{O}(f^2L^f)$ to $\widetilde{O}(f^{\frac{5}{2}} L^{o(1)})$. It also improves over the size and query time of the $(L,f)$-RPC by Karthik and Parter [SODA 2021] by nearly a factor of $L$. We then derive oracles for $L$-Hop Shortest Path, $k$-Path, and $k$-Clique from this. Notably, our solution for $k$-Path improves the query time of the one by Bilò, et al. [ITCS 2022] for $f=o(\log k)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_17776 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks Bilò, Davide Choudhary, Keerti Cohen, Sarel Friedrich, Tobias Schirneck, Martin Data Structures and Algorithms We design sensitivity oracles for error-prone networks. For a network problem $Π$, the data structure preprocesses a network $G=(V,E)$ and sensitivity parameter $f$ such that, for any set $F\subseteq V\cup E$ of up to $f$ link or node failures, it can report a solution for $Π$ in $G{-}F$. We study three network problems $Π$. $L$-Hop Shortest Path: Given $s,t \in V$, is there a shortest $s$-$t$-path in $G-F$ with at most $L$ links? $k$-Path: Does $G-F$ contain a simple path with $k$ links? $k$-Clique: Does $G-F$ contain a clique of $k$ nodes? Our main technical contribution is a new construction of $(L,f)$-replacement path coverings ($(L,f)$-RPC) in the parameter realm where $f = o(\log L)$. An $(L,f)$-RPC is a family $\mathcal{G}$ of subnetworks of $G$ which, for every $F \subseteq E$ with $|F| \le f$, contain a subfamily $\mathcal{G}_F \subseteq \mathcal{G}$ such that (i) no subnetwork in $\mathcal{G}_F$ contains a link of $F$ and (ii) for each $s,t \in V$, if $G-F$ contains a shortest $s$-$t$-path with at most $L$ links, then some subnetwork in $\mathcal{G}_F$ retains at least one such path. Our $(L, f)$-RPC has almost the same size as the one by Weimann and Yuster [ACM TALG 2013] but it improves the time to query $\mathcal{G}_F$ from $\widetilde{O}(f^2L^f)$ to $\widetilde{O}(f^{\frac{5}{2}} L^{o(1)})$. It also improves over the size and query time of the $(L,f)$-RPC by Karthik and Parter [SODA 2021] by nearly a factor of $L$. We then derive oracles for $L$-Hop Shortest Path, $k$-Path, and $k$-Clique from this. Notably, our solution for $k$-Path improves the query time of the one by Bilò, et al. [ITCS 2022] for $f=o(\log k)$. |
| title | Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.17776 |