Abstract
Constrained Forest Problems (CFPs) capture a wide range of network design problems, including Minimum Spanning Tree, Steiner Forest, and Point-to-Point Connection. While these have been studied extensively in isolation, a unified approach across different computational models has been lacking. We present the shell-decomposition algorithm, a model-agnostic meta-algorithm that efficiently computes a $(2+\epsilon)$-approximation for a broad class of forest functions. We demonstrate its flexibility by instantiating it for fundamental NP-hard CFPs in distributed (CONGEST), parallel (PRAM), and streaming models, achieving near-universal optimality in many settings.
Introduction
Network design often involves finding a minimum-weight set of edges to satisfy specific connectivity constraints. These are formalized as Constrained Forest Problems (CFPs). Traditionally, algorithms for CFPs are tailored to specific computational models (e.g., distributed vs. parallel) and specific problem variants. This model-specificity forces researchers to reinvent solutions for every new environment. Furthermore, traditional complexity often focuses on worst-case graphs, ignoring the potential for "universal optimality" where performance scales with the actual topology of the network.
The Shell-Decomposition Algorithm
The core contribution of this work is the shell-decomposition algorithm. Rather than solving a CFP directly, it reduces the problem into four fundamental building blocks:
- Approximate Set-Source Shortest-Path Forest (aSSSP)
- Minimum Spanning Tree (MST)
- Root-Path Selection (RPS)
- Forest-Function Evaluation (FFE)
By abstracting these components, the algorithm becomes model-agnostic; any improvement in the underlying algorithms for these blocks (like a faster MST) automatically translates to a faster CFP solver.
Primal-Dual Innovations
The algorithm modernizes the classic Goemans-Williamson (GW) primal-dual framework with three key modifications:
- Incremental Construction: Components are merged immediately upon contact during the growth phase.
- Approximate Distances: Using $(1+\epsilon)$ distance approximations accelerates computation with minimal loss in solution quality.
- Deferred Evaluation: The "forest function" is evaluated only at specific intervals (powers of $1+\epsilon$), significantly reducing communication overhead in distributed settings.
Distributed Complexity and Universal Optimality
In the CONGEST model, the algorithm's performance is tied to the complexity of Partwise Aggregation ($T^{PA}$), a measure of how efficiently information can be aggregated over disjoint connected components. This allows the algorithm to bypass the standard $\sqrt{n} + D$ lower bounds on specific topologies, achieving near-universal optimality.
As shown in Table 1, the algorithm handles various input models for Steiner Forest. For instance, in the Symmetric Connection Request (SF-SCR) variant, randomized equality testing is used to achieve a running time of $\tilde{O}(\sqrt{n} + D)$, bypassing deterministic lower bounds.
Results and Comparison
The shell-decomposition framework provides a $(2+\epsilon)$-approximation for any CFP with a "proper" forest function. The results across different problems and models are summarized below.
Key highlights include:
- CONGEST: Achieves $\tilde{O}(\sqrt{n} + D + k)$ for Steiner Forest and $\tilde{O}(\sqrt{n} + D)$ for Point-to-Point Connection (PPC) and Facility Placement and Connection (FPC).
- PRAM: Requires $O(\epsilon^{-3}m)$ work and $O(\epsilon^{-3})$ depth.
- Streaming: Operates in $O(\epsilon^{-3})$ passes with $O(n)$ memory.
Conclusion
The shell-decomposition algorithm provides a unified, efficient framework for approximating Constrained Forest Problems across diverse computational models. By reducing complex problems to standard building blocks and leveraging topology-aware aggregation, it achieves state-of-the-art results and moves closer to universal optimality. Future work includes extending the framework to "uncrossable" functions and exploring its application in hypergraph design.
Summary updated