decremental

Decremental is an adjective meaning characterized by a tendency to decrease. In mathematics and computer science, it describes processes, datasets, or algorithms in which the relevant parameter only decreases over time, typically through deletions rather than insertions. A decremental problem is one where the instance evolves by removing elements, and the goal is to maintain a particular property or answer efficiently after each removal.

In the field of graph algorithms, decremental refers to dynamic graph algorithms that support deletions of edges or vertices but not insertions. The central challenge is to update the maintained structure or query results—such as connectivity, shortest paths, spanning trees, or reachability—without recomputing from scratch. Decremental methods often rely on careful data structures and amortized analysis; in some cases, fully dynamic or incremental approaches offer alternative trade-offs.

Typical problems include decremental connectivity, decremental single-source shortest paths, and decremental minimum spanning trees. In some settings, exact solutions are expensive, and algorithms maintain approximate results to achieve faster update times. Decremental algorithms are used in network reliability studies, real-time planning, and dynamic systems where deletions occur naturally (e.g., failed connections, removed routes).

Relation with other terms: decremental is contrasted with incremental (insertions only) and fully dynamic (insertions and deletions). It is also used more generally to describe processes that monotonically decrease a quantity, such as a residual budget or potential function, in various mathematical or computational contexts.