2026-07-23T04:26:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20204 2024-07-02T07:52:51Z ddc:004 open_access

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs Feldmann, Andreas Emil Lampis, Michael Steiner Forest Approximation Algorithms FPT algorithms In this paper 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, Hajiaghayi and Marx [JACM, 2011] gave an approximation scheme with a runtime of n^O(k²/ε) on graphs of treewidth k. Our main result is a much faster efficient parameterized approximation scheme (EPAS) with a runtime of 2^O(k²/ε log k/ε)⋅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(k log k)⋅n^O(1) time, and we also prove that this runtime 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andreas Emil Feldmann and Michael Lampis 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.61 urn:nbn:de:0030-drops-202048 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.61 eng https://creativecommons.org/licenses/by/4.0/legalcode