Abstract
In this paper, we consider Steiner forest and its generalizations, prize-collecting Steiner forest and k-Steiner forest, when the vertices of the input graph are points in the Euclidean plane and the lengths are Euclidean distances. First, we present a simpler analysis of the polynomial-time approximation scheme (PTAS) of Borradaile et al. [12] for the Euclidean Steiner forest problem. This is done by proving a new structural property and modifying the dynamic programming by adding a new piece of information to each dynamic programming state. Next we develop a PTAS for a well-motivated case, i.e., the multiplicative case, of prize-collecting and budgeted Steiner forest. The ideas used in the algorithm may have applications in design of a broad class of bicriteria PTASs. At the end, we demonstrate why PTASs for these problems can be hard in the general Euclidean case (and thus for PTASs we cannot go beyond the multiplicative case).
Introduction
The Steiner Forest problem is a fundamental challenge in network design, requiring the minimum-cost set of edges to connect specific pairs of "terminal" points. While the problem is NP-hard in general, its Euclidean variant—where points reside in a 2D plane—offers more geometric structure. This paper investigates two significant generalizations:
- Prize-collecting Steiner Forest (PCSF): Instead of connecting every pair, one can pay a penalty (prize) for leaving a pair disconnected. The goal is to minimize the sum of edge costs and penalties.
- $k$-Steiner Forest: A requirement to connect at least $k$ pairs at minimum cost.
While Polynomial-Time Approximation Schemes (PTASs) existed for basic Euclidean Steiner Forest, their analyses were complex. This work simplifies these proofs and extends the PTAS framework to the "multiplicative" version of the prize-collecting variant.
Methods
The algorithmic framework relies on a random dissection technique, partitioning the plane into a quadtree-like hierarchy of squares.
Key technical contributions include:
- The Locality Property: A structural theorem showing that near-optimal solutions exist where terminals in a small cell connected to the boundary are also connected to each other within that cell.
- Bitmap-based Dynamic Programming: The authors replace complex path-based connectivity tracking with a simple $\gamma \times \gamma$ bitmap. This streamlines the state space of the dynamic programming (DP) table and simplifies the proof of correctness.
- Weight Rounding for Multiplicative Prizes: In the "multiplicative case"—where the penalty for a pair $(u, v)$ is $\phi(u)\phi(v)$—the authors round weights to multiples of a value $\theta$. This keeps the DP table size polynomial while ensuring a $(1+\epsilon)$ approximation.
Key Insights
- Algorithmic Simplicity: Transitioning from "enclosing paths" to "bitmaps" makes the proof more robust and accessible for future research.
- The Multiplicative Constraint: The multiplicative structure allows the algorithm to track total prizes through the sums of weights within connected components, making the problem tractable where the general case is not.
- Floating-point DP: To handle asymmetric prizes, the authors use a technique similar to floating-point representation (storing a coefficient and a variable unit), preventing the DP table from exploding.
Results and Hardness
The paper establishes several key theoretical results:
- Theorem 1: Provides a simplified PTAS analysis for the Euclidean Steiner Forest.
- Theorems 2 & 3: Introduce the first PTAS for the Multiplicative Prize-collecting Steiner Forest (MPCSF), achieving a bicriteria $(1+\epsilon, 1-\epsilon')$-approximation.
- Hardness of Approximation: The authors show that the $k$-forest problem in high-dimensional Euclidean space ($d > 8$) is related to the "notorious" densest $k$-subgraph problem, suggesting that a general PTAS for non-multiplicative cases is unlikely.
Conclusion
This work advances the understanding of Euclidean network design by simplifying existing PTAS analyses and extending them to prize-collecting variants. While the multiplicative case is now solvable with a PTAS, the general Euclidean PCSF remains a challenge, with evidence suggesting APX-hardness in higher dimensions. Future work includes extending these techniques to planar graphs and improving approximation factors for general graphs.
Summary updated