Multi-level Steiner Trees

Abu Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh, Alon Efrat, David Glickenstein, Martin Gronemann, Niklas Heinsohn, Stephen G. Kobourov, Richard Spence, Joseph Watkins, Alexander Wolff

TL;DR

This paper introduces and analyzes the Multi-Level Steiner Tree (MLST) problem, a generalization of the classic Steiner Tree problem where terminals are organized into hierarchical levels. The authors propose novel approximation algorithms and ILP formulations, achieving state-of-the-art approximation ratios for this problem, particularly for a large number of levels.

What Problem Does This Paper Address?

The classic Steiner Tree (ST) problem aims to find the minimum-cost tree connecting a set of terminal nodes in a graph. While well-studied, it has limitations in real-world scenarios where services or network requirements have different "grades" or "levels." The Multi-Level Steiner Tree (MLST) problem addresses this by introducing a hierarchy of terminal sets ($T_l \subseteq T_{l-1} \subseteq \dots \subseteq T_1 \subseteq V$), where edges can be used at multiple levels, incurring costs based on the highest level they support. This is relevant for applications like multi-tier network design and graph visualization. The challenge lies in efficiently finding optimal or near-optimal solutions for this more complex problem, especially as the number of levels increases.

Methods

The paper presents several algorithmic approaches:

  • Top-Down and Bottom-Up Heuristics: These are straightforward approaches that build the MLST by either starting from the highest level and propagating downwards, or starting from the lowest level and propagating upwards. They provide $O(l)$-approximations.
  • Composite Heuristic: This approach generalizes the top-down and bottom-up methods by considering various combinations of intermediate levels. It achieves better approximation ratios but requires a large number of Steiner tree computations ($2^{l-1}$).
  • Guaranteed Performance Heuristic (CMP(Q*)): To address the computational cost of the composite heuristic, this method finds a specific subset of levels ($Q^*$) that guarantees the same approximation ratio with significantly fewer Steiner tree computations (at most $2l$).
  • Integer Linear Programming (ILP) Formulations: The authors propose several ILP formulations for MLST, including cut-based and flow-based approaches, which can be used to find optimal solutions for smaller instances or to analyze approximation ratios.

Datasets

The authors synthesized graph data using three standard network generation models:

  • Erdős-Rényi (ER): Randomly assigns edges with a given probability.
  • Watts-Strogatz (WS): Creates small-world networks with high clustering.
  • Barabási-Albert (BA): Generates scale-free networks with a power-law degree distribution.

For each model, they generated graphs of varying sizes ($|V| = 50, 100, \dots, 500$) and assigned random integer edge weights. MLST instances were created with $l = 2, 3, 4, 5$ levels, using two terminal selection strategies: linear (decreasing terminal set sizes linearly) and exponential (decreasing sizes exponentially).

Key Insights and Ideas

  • Hierarchical Structure Matters: The MLST problem's hierarchical nature allows for more cost-effective solutions than simply solving independent Steiner trees for each level. Edges can be reused across levels, with costs reflecting their highest usage.
  • Composite Heuristic Power: Combining top-down and bottom-up strategies by strategically selecting intermediate levels (as in the composite heuristic) yields significantly better approximation ratios than either standalone approach.
  • Computational Trade-off: The initial composite heuristic offers excellent theoretical guarantees but is computationally expensive. The CMP(Q*) heuristic cleverly balances approximation quality with computational feasibility by reducing the number of required Steiner tree computations.
  • ILP for Analysis and Exact Solutions: The ILP formulations are crucial for both proving theoretical bounds and for obtaining exact optimal solutions to benchmark heuristic performance, especially for smaller problem instances.

Key Results

  • The paper provides theoretical guarantees for approximation ratios: $O(l)$ for basic top-down/bottom-up, and a more refined ratio for the composite heuristic, which is shown to be better than previous results for up to $l=100$ levels.
  • The composite heuristic (CMP) achieved the best practical performance in experiments, closely followed by CMP(Q*).
  • The performance of heuristics slightly degrades as the number of levels ($l$) increases.
  • Exponential terminal selection (leading to smaller terminal sets at higher levels) resulted in slightly worse heuristic performance compared to linear selection.
  • The running time for computing exact solutions (using ILP) increases significantly with the number of levels and graph size, highlighting the need for efficient approximation algorithms.
  • Using a 2-approximation algorithm for the single-level Steiner tree subroutine did not significantly impact the performance of the MLST heuristics compared to using an exact solver.

Limitations and Future Work

  • Inapproximability: The paper poses the question of whether stronger inapproximability results exist for MLST compared to the standard ST problem.
  • Tightness of Ratios: It remains an open question whether the derived approximation ratios for the composite heuristic are tight for all values of $l$.
  • Generalization: The authors wonder if the results can be generalized to other "sparsifiers" beyond Steiner trees, such as node-weighted Steiner trees or graph t-spanners.
  • Direct Approximation: Investigating whether MLST can be approximated directly, without relying on multiple single-level ST subroutines, is suggested.
  • Worst-Case Instance Design: Exploring if the LP formulation's output can aid in designing worst-case instances for MLST is another avenue for future research.

Summary updated

Abstract

In the classical Steiner tree problem, given an undirected, connected graph $G=(V,E)$ with non-negative edge costs and a set of \emph{terminals} $T\subseteq V$, the objective is to find a minimum-cost tree $E' \subseteq E$ that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of $ρ= \ln(4)+\varepsilon < 1.39$. In this paper, we study a natural generalization, the \emph{multi-level Steiner tree} (MLST) problem: given a nested sequence of terminals $T_{\ell} \subset \dots \subset T_1 \subseteq V$, compute nested trees $E_{\ell}\subseteq \dots \subseteq E_1\subseteq E$ that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under various names including Multi-level Network Design, Quality-of-Service Multicast tree, Grade-of-Service Steiner tree, and Multi-Tier tree. Several approximation results are known. We first present two simple $O(\ell)$-approximation heuristics. Based on these, we introduce a rudimentary composite algorithm that generalizes the above heuristics, and determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio using at most $2\ell$ Steiner tree computations. We compare these heuristics experimentally on various instances of up to 500 vertices using three different network generation models. We also present various integer linear programming (ILP) formulations for the MLST problem, and compare their running times on these instances. To our knowledge, the composite algorithm achieves the best approximation ratio for up to $\ell=100$ levels, which is sufficient for most applications such as network visualization or designing multi-level infrastructure.
BibTeX
@article{ahmed2019multi,
  author = {Abu Reyan Ahmed and Patrizio Angelini and Faryad Darabi Sahneh and Alon Efrat and David Glickenstein and Martin Gronemann and Niklas Heinsohn and Stephen G. Kobourov and Richard Spence and Joseph Watkins and Alexander Wolff},
  title = {{Multi-level Steiner Trees}},
  journal = {ACM J. Exp. Algorithmics},
  year = {2019},
  doi = {10.1145/3368621},
}
Figure