Parameterized Algorithms for Steiner Forest in Bounded Width Graphs

2024/02/15 by Andreas Emil Feldmann, Michael Lampis, Feldmann, Andreas Emil +1 · 1 voice
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Interconnection Networks and Systems

paper · pdf · doi:10.1145/3748724

openalex publication_date 2025/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

In this article, we reassess the parameterized complexity and approximability of the well-studied Steiner Forest problem in several graph classes of bounded width. The problem takes an edge-weighted graph and pairs of vertices as input, and the aim is to find a minimum cost subgraph in which each given vertex pair lies in the same connected component. It is known that this problem is APX-hard in general, and NP-hard on graphs of treewidth 3, treedepth 4, and feedback vertex set size 2. However, Bateni et al. gave an approximation scheme with a run time of \(n^O(k²/ε)\) on graphs of treewidth \( k \) . Our main result is a much faster Efficient Parameterized Approximation Scheme (EPAS) with a run time of \(2^O(\frack²εlog\frackε) ⋅ n^O(1)\) . If \( k \) instead is the vertex cover number of the input graph, we show how to compute the optimum solution in \(2^{O(klog k)} ⋅ n^O(1)\) time, and we also prove that this run-time dependence on \( k \) is asymptotically best possible, under ETH. Furthermore, if \( k \) is the size of a feedback edge set, then we obtain a faster \(2^O(k)⋅ n^O(1)\) time algorithm, which again cannot be improved under ETH.

Citations

• Steiner Tree Approximation via Iterative Randomized Rounding
• Which Problems Have Strongly Exponential Complexity?
• Approximation algorithms for NP-complete problems on planar graphs
• Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem
• Structural Parameterizations for Two Bounded Degree Problems Revisited
• Parameterized Max Min Feedback Vertex Set
• Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity
• A Survey on Approximation in Parameterized Complexity: Hardness and\n Algorithms
• Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces
• Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
• An efficient polynomial-time approximation scheme for Steiner forest in planar graphs
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• The Steiner tree problem on graphs: Inapproximability results
• Fourier meets Möbius: fast subset convolution

Discussions

• 📖 New LAMSADE paper: Parameterized Algorithms for Steiner Forest in Bounded Width Graphs. (ACM Trans. Algorithms) https://doi.org/10.1145/3748724 [bsky, 0 points, 0 comments]