Online Steiner Tree with Deletions

Anupam Gupta, Amit Kumar

Abstract

In the online Steiner tree problem, terminals arrive sequentially, and an algorithm must maintain a spanning tree over the current set of terminals. While additions-only models are well-understood, the introduction of vertex deletions presents significant challenges for maintaining both a low competitive ratio and low recourse (the number of edge changes). This paper presents two primary results: a deletions-only algorithm that maintains a constant competitive ratio with $O(1)$ non-amortized edge changes per request, and a fully-dynamic algorithm that achieves constant competitiveness with $O(1)$ amortized edge changes. These results utilize primal-dual hierarchical clustering and greedy swap mechanisms to overcome the limitations of previous $O(n^{3/2})$ recourse bounds.

Introduction

The Steiner Tree Problem is a fundamental optimization challenge: given a set of terminal vertices in a metric space, find the minimum-cost tree that connects them. In the online version, the set of terminals changes over time. Historically, online algorithms without the ability to modify existing edges (recourse) were limited to a competitive ratio of $\Theta(\log n)$. To achieve a constant competitive ratio—where the tree's cost is within a fixed factor of the optimal Steiner tree—algorithms must be allowed to "rewire" or swap edges as terminals arrive or depart.

While recent breakthroughs established that constant recourse is sufficient to handle vertex additions, the problem of vertex deletions remained largely open. Deleting a vertex can disconnect the tree or render existing paths inefficient. Recomputing the tree from scratch would maintain optimality but at the cost of high recourse, potentially changing $O(n)$ edges per step. This paper addresses how to maintain a high-quality Steiner tree under deletions and fully-dynamic updates with minimal structural changes.

The Deletions-Only Model: Primal-Dual Hierarchical Clustering

The first major contribution of this work is an algorithm for the deletions-only setting. The algorithm begins with a complete set of terminals and handles their sequential removal.

The "Zombie" Strategy

To maintain stability, the algorithm introduces the concept of "zombie" nodes. When a terminal is deleted, it is not immediately removed from the underlying data structure. Instead, it becomes a zombie, continuing to participate in the connectivity of the tree and the growth of "dual moats" within a primal-dual framework. This prevents the tree from undergoing massive reconfigurations every time a terminal is removed.

Pruning and Non-Amortized Recourse

To prevent the cost of the tree from becoming dominated by edges connecting zombies, the algorithm monitors the ratio of active terminals to zombies within a hierarchical clustering structure. When a specific level of the hierarchy becomes "bad" (containing too many zombies), the algorithm performs a pruning step.

To achieve a non-amortized bound—guaranteeing $O(1)$ changes for every deletion—the authors employ a "skeleton graph" argument. By identifying low-degree zombie clusters in the forest, the algorithm can localize rewiring. This ensures that the structural updates required to maintain a constant competitive ratio are distributed evenly across deletion requests, avoiding the large bursts of changes typical of amortized algorithms.

The Fully-Dynamic Model: Greedy Swaps

The second result addresses the fully-dynamic model, where terminals can be both added and deleted. The authors analyze a natural greedy algorithm originally proposed by Imase and Waxman.

C-Swaps and Extension Trees

The algorithm maintains a constant competitive ratio by performing "c-swaps." If a non-tree edge is found to be significantly cheaper than a tree edge it could replace, the algorithm performs a swap to improve the total cost. To bound the recourse, the authors utilize an "extension tree" where Steiner (non-terminal) vertices are required to have a degree of at least 3. This structural constraint limits the number of Steiner vertices relative to terminals, allowing the authors to prove that the algorithm makes only a constant number of changes per request in an amortized sense.

Key Results and Impact

The paper establishes two significant bounds for the dynamic Steiner tree problem:

  1. Deletions-Only: Constant competitive ratio with $O(1)$ non-amortized recourse.
  2. Fully-Dynamic: Constant competitive ratio with $O(1)$ amortized recourse.

These results represent a major improvement over the $O(n^{3/2})$ recourse bound established in the early 1990s. By demonstrating that constant recourse is sufficient for dynamic updates, this work bridges the gap between theoretical online algorithms and practical network design where stability and efficiency are both paramount.

Conclusion and Future Work

This research provides a robust framework for maintaining Steiner trees in dynamic environments. However, several open questions remain. While the deletions-only result is non-amortized, the fully-dynamic result remains amortized; finding a non-amortized algorithm for the fully-dynamic case is a key open problem. Additionally, extending these techniques to the Steiner Forest problem—where multiple disjoint sets of terminals must be connected—remains a promising direction for future research.

Summary updated

Abstract

In the online Steiner tree problem, the input is a set of vertices that appear one-by-one, and we have to maintain a Steiner tree on the current set of vertices. The cost of the tree is the total length of edges in the tree, and we want this cost to be close to the cost of the optimal Steiner tree at all points in time. If we are allowed to only add edges, a tight bound of $\Theta(\log n)$ on the competitiveness is known. Recently it was shown that if we can add one new edge and make one edge swap upon every vertex arrival, we can maintain a constant-competitive tree online. But what if the set of vertices sees both additions and deletions? Again, we would like to obtain a low-cost Steiner tree with as few edge changes as possible. The original paper of Imase and Waxman had also considered this model, and it gave a greedy algorithm that maintained a constant-competitive tree online, and made at most $O(n^{3/2})$ edge changes for the first $n$ requests. In this paper give the following two results. Our first result is an online algorithm that maintains a Steiner tree only under deletions: we start off with a set of vertices, and at each time one of the vertices is removed from this set: our Steiner tree no longer has to span this vertex. We give an algorithm that changes only a constant number of edges upon each request, and maintains a constant-competitive tree at all times. Our algorithm uses the primal-dual framework and a global charging argument to carefully make these constant number of changes. We then study the natural greedy algorithm proposed by Imase and Waxman that maintains a constant-competitive Steiner tree in the fully-dynamic model (where each request either adds or deletes a vertex). Our second result shows that this algorithm makes only a constant number of changes per request in an amortized sense.
BibTeX
@inproceedings{gupta2014online,
  author = {Anupam Gupta and Amit Kumar},
  title = {{Online Steiner Tree with Deletions}},
  booktitle = {SODA},
  year = {2014},
  doi = {10.1137/1.9781611973402.34},
}
Figure