Model-Agnostic Approximation of Constrained Forest Problems

Corinna Coupette, Alipasha Montaseri, Christoph Lenzen

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:

  1. Approximate Set-Source Shortest-Path Forest (aSSSP)
  2. Minimum Spanning Tree (MST)
  3. Root-Path Selection (RPS)
  4. 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.

Table 1: Complexity of Steiner Forest variants under different input specifications and models.

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.

Table 2: Comparison of the proposed work against previous state-of-the-art for fundamental CFPs.

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

Abstract

Constrained Forest Problems (CFPs) as introduced by Goemans and Williamson in 1995 capture a wide range of network design problems with edge subsets as solutions, such as Minimum Spanning Tree, Steiner Forest, and Point-to-Point Connection. While individual CFPs have been studied extensively in individual computational models, a unified approach to solving general CFPs in multiple computational models has been lacking. Against this background, we present the shell-decomposition algorithm, a model-agnostic meta-algorithm that efficiently computes a $(2+\epsilon)$-approximation to CFPs for a broad class of forest functions. To demonstrate the power and flexibility of this result, we instantiate our algorithm for 3 fundamental, NP-hard CFPs in 3 different computational models. For example, for constant $\epsilon$, we obtain the following $(2+\epsilon)$-approximations in the Congest model: 1. For Steiner Forest specified via input components, where each node knows the identifier of one of $k$ disjoint subsets of $V$, we achieve a deterministic $(2+\epsilon)$-approximation in $O(\sqrt{n}+D+k)$ rounds, where $D$ is the hop diameter of the graph. 2. For Steiner Forest specified via symmetric connection requests, where connection requests are issued to pairs of nodes, we leverage randomized equality testing to reduce the running time to $O(\sqrt{n}+D)$, succeeding with high probability. 3. For Point-to-Point Connection, we provide a $(2+\epsilon)$-approximation in $O(\sqrt{n}+D)$ rounds. 4. For Facility Placement and Connection, a relative of non-metric Facility Location, we obtain a $(2+\epsilon)$-approximation in $O(\sqrt{n}+D)$ rounds. We further show how to replace the $\sqrt{n}+D$ term by the complexity of solving Partwise Aggregation, achieving (near-)universal optimality in any setting in which a solution to Partwise Aggregation in near-shortcut-quality time is known.
BibTeX
@inproceedings{coupette2025model,
  author = {Corinna Coupette and Alipasha Montaseri and Christoph Lenzen},
  title = {{Model-Agnostic Approximation of Constrained Forest Problems}},
  booktitle = {DISC},
  year = {2025},
  doi = {10.4230/lipics.disc.2025.25},
}
Figure