Sensitive incremental

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