sensitive incremental #SSR (Vertex Reachability)
Description
A data structure with sensitivity $d$ for a problem $P$ has the following properties: It obtains an instance $p$ of $P$ and is allowed polynomial preprocessing time on $p$. After the preprocessing, the data structure must provide the following operations:
(Batch) Update: Up to $d$ changes are performed to the initial problem instance $p$, e.g., $d$ edges are added to or removed from $p$.
Query: The user queries a specific property about the instance of the problem after the last update, e.g., the shortest path between two nodes avoiding the edges deleted in the last update.
In the incremental version of these problems, the batch update adds edges to $p$.
Related Problems
Generalizations: #SSR
Related: ST-Reach, st-Reach, constant sensitivity incremental ST-Reach, 1-sensitive incremental ss-reach, 2-sensitive incremental st-reach, ap-reach
Parameters
n: number of vertices
m: number of edges
d: sensitivity
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| CNF-SAT | assume: SETH then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$ |
2017 | https://arxiv.org/pdf/1703.01638.pdf | link |