Till innehåll på sidan

Andreas Emil Feldmann: Parameterized Algorithms for Steiner Forest in Bounded Width Graphs

Tid: On 2024-04-10 kl 13.15 - 14.00

Plats: KTH, 1440 (Henrik Eriksson), Lindstedtsvägen 3 (E-huset)

Medverkande: Andreas Emil Feldmann (University of Sheffield)

Exportera till kalender

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