Dynamic Detours

Fix a parameter $k \in \mathbb{N}$. We give dynamic data structures that for a fully dynamic undirected graph $G$, updated over time by edge insertions and edge deletions, can answer the following queries: - Long ($u,v$)-path: Given $u,v \in V(G)$, is there a path from $u$ to $v$ of length at least $k$? - Long ($u,v$)-detour: Given $u,v \in V(G)$, is there a path from $u$ to $v$ of length at least $\mathsf{dist}_{G}(u,v)+k$? - Even/odd ($u,v$)-path: Given $u,v \in V(G)$, is there a path from $u$ to $v$ of even/odd length? The amortized time of executing an update or answering a query is $2^{\mathcal{O}(k^3)} \log n + \mathcal{O}(\log^2 n \log^2 \log n)$ in the first two cases, and $\mathcal{O}(\log^2 n \log^2 \log n)$ in the last, where $n$ is the number of vertices of $G$. The first result is in sharp contrast with known conditional lower bounds for reporting paths of length at most $k$. Specifically, there is no data structure supporting queries about ($u,v$)-paths of length at most two in time $n^{o(1)}$ unless the Triangle Conjecture fails. Our main technical contribution is a mechanism of "delayed edge insertion" that works locally on the level of biconnected components.

• View at Publisher
• View at Scopus

Free Full Text ( Final Version , 1mb )