# Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window)

arXiv: https://arxiv.org/abs/2211.05178 · HTML: https://mlsanity.com/paper/2211.05178/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2022.

## Built on by (most cited first, 1 of 1)

- [Incremental Approximate Single-Source Shortest Paths with Predictions](https://mlsanity.com/paper/2502.08125/) (2025)

## Abstract (arXiv)

Dynamic algorithms come in three main flavors: mathitincremental (insertions-only), mathitdecremental (deletions-only), or mathitfully mathitdynamic (both insertions and deletions). Fully dynamic is the holy grail of dynamic algorithm design; it is obviously more general than the other two, but is it strictly harder? Several works managed to reduce fully dynamic to the incremental or decremental models by taking advantage of either specific structure of the incremental/decremental algorithms (e.g. [HK99, HLT01, BKS12, ADKKP16, BS80, OL81, OvL81]), or specific order of insertions/deletions (e.g. [AW14,HKNS15,KPP16]). Our goal in this work is to get a black-box fully-to-incremental reduction that is as general as possible. We find that the following conditions are necessary: bullet The incremental algorithm must have a worst-case (rather than amortized) running time guarantee. bullet The reduction must work in what we call the mathitdeletions-mathitlook-mathitahead mathitmodel, where the order of deletions among current elements is known in advance. A notable practical example is the "sliding window" (FIFO) order of updates. Under those conditions, we design: bullet A simple, practical, amortized-fully-dynamic to worst-case-incremental reduction with a log(T)-factor overhead on the running time, where T is the total number of updates. bullet A theoretical worst-case-fully-dynamic to worst-case-incremental reduction with a mathsfpolylog(T)-factor overhead on the running time.