Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality

Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg, Sushant Sachdeva

Introduction

In the field of dynamic graph algorithms, achieving "almost-linear" time complexity—where the total processing time for a sequence of updates is nearly proportional to the size of the graph—is considered a gold standard. While recent breakthroughs have achieved this for incremental updates (adding edges), the decremental setting (deleting edges) has remained a formidable challenge. This paper, authored by a collaborative team from Georgia Tech, CMU, ETH Zurich, IAS, and the University of Toronto, presents a landmark result: the first almost-linear time algorithm for the decremental minimum-cost flow problem.

The Feasibility Gap: Incremental vs. Decremental

Dynamic graph problems are categorized by the types of updates they support. In the incremental model, edges are added or capacities increased. In the decremental model, edges are removed or capacities decreased.

The fundamental difficulty in maintaining a minimum-cost flow decrementally lies in the concept of feasibility. In an incremental setting, if a flow is valid, adding a new edge does not invalidate it; it merely provides more options for optimization. However, in a decremental setting, deleting an edge is akin to breaking a pipe in a network. If that edge was carrying flow, the current solution immediately becomes infeasible. Re-establishing feasibility while maintaining optimality has traditionally required significant recomputation, preventing previous algorithms from reaching almost-linear efficiency.

The Dual Breakthrough: From Flows to Voltages

The authors bypass the feasibility crisis by pivoting from the primal problem (flow) to its dual (vertex potentials). In the dual space of the min-cost flow problem, variables are viewed as "voltages" at each vertex.

The critical insight is that while edge deletions destroy primal feasibility, they preserve dual feasibility. If a set of vertex potentials satisfies the condition that the voltage drop across any edge does not exceed its cost, that condition remains satisfied even if some edges are removed from the graph. This monotonicity allows the researchers to employ an $\ell_1$-Interior Point Method (IPM) on the dual problem, maintaining an approximate solution efficiently as the graph shrinks.

Technical Innovations: The Algorithmic Pipeline

To implement this dual-based approach, the paper introduces several sophisticated algorithmic components:

  1. Dynamic Min-Ratio Cut: The dual IPM relies on solving a sequence of sub-problems that identify the "best" cut in the graph relative to current gradients. The authors developed a dynamic version of this to handle the changing graph structure.
  2. Capacitated Expander Hierarchies: A major technical hurdle was maintaining expander decompositions—clusters of well-connected nodes—in graphs with varying edge capacities. Previous techniques were largely restricted to "unit capacity" graphs. The authors developed a new hierarchy capable of handling arbitrary capacities, which proved to be simpler and more efficient than the distance-based tools used in incremental algorithms.
  3. Tree Cut Sparsifiers: To accelerate the cut problems, the algorithm maintains a tree structure that approximates the overall cut geometry of the graph, allowing for fast updates.

Key Results and Impact

The framework yields several state-of-the-art results:

  • Decremental Min-Cost Flow: The algorithm processes $Q$ updates in a total time of $(m+Q)m^{o(1)}$, where $m$ is the number of edges. The $m^{o(1)}$ factor represents a growth rate slower than any fixed power of $m$, effectively achieving almost-linear performance.
  • Static Algorithm Speedup: Interestingly, the dual-based approach is so efficient that it sets new records for static min-cost flow, outperforming previous randomized and deterministic algorithms on fixed graphs.
  • Strongly Connected Components (SCCs): The paper provides a deterministic algorithm for maintaining SCCs in $m^{1+o(1)}$ time. This is a significant improvement over the previous best complexity of approximately $m\sqrt{n}$.
  • Deterministic Robustness: Unlike many modern dynamic algorithms that rely on randomization and assume an "oblivious adversary" (one who doesn't see the algorithm's internal state), these algorithms are deterministic. They remain robust regardless of the update sequence chosen.

Conclusion and Future Work

By shifting the perspective from primal flow to dual voltages, the authors have resolved a long-standing open problem in dynamic graph theory. The transition from "distance geometry" (used in incremental settings) to "cut geometry" (using expanders) appears to be the key to unlocking decremental efficiency.

While the results are transformative, some constraints remain. The algorithm assumes edge costs and capacities are polynomially bounded integers. Furthermore, while the algorithm can maintain distances and SCC memberships, it does not yet explicitly output the "witness paths" or specific flow assignments during the updates. Future research may extend this framework to provide these explicit witnesses and further bridge the gap between directed and undirected sub-problems.

Summary updated

BibTeX
@inproceedings{brand2024almost,
  author = {Jan van den Brand and Li Chen and Rasmus Kyng and Yang P. Liu and Simon Meierhans and Maximilian Probst Gutenberg and Sushant Sachdeva},
  title = {{Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality}},
  booktitle = {FOCS},
  year = {2024},
  doi = {10.1109/focs61266.2024.00120},
}
Figure