Andreas Emil Feldmann: Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
Time: Wed 2024-04-10 13.15 - 14.00
Location: KTH, 1440 (Henrik Eriksson), Lindstedtsvägen 3 (E-huset)
Participating: Andreas Emil Feldmann (University of Sheffield)
Abstract:
We study the parameterized complexity of the well-studied Steiner Forest problem in graphs of bounded treewidth. 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\). However, Bateni et al. [JACM, 2011] gave an approximation scheme with a runtime of \(n^{O(k^2/\varepsilon)}\) on graphs of treewidth \(k\). Our main result is a much faster efficient parameterized approximation scheme (EPAS) with a runtime of \(2^{O(k^2/\varepsilon \log(k/\varepsilon))} n^{O(1)}\).
This is joint work with Michail Lampis. arxiv.org/pdf/2402.09835.pdf