2026-07-22T06:50:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21147 2024-09-23T09:13:18Z ddc:004 open_access

Steiner Tree Parameterized by Multiway Cut and Even Less Jansen, Bart M.P. Swennenhuis, Céline M.F. fixed-parameter tractability Steiner Tree structural parameterization H-treewidth In the Steiner Tree problem we are given an undirected edge-weighted graph as input, along with a set K of vertices called terminals. The task is to output a minimum-weight connected subgraph that spans all the terminals. The famous Dreyfus-Wagner algorithm running in 3^{|K|}poly(n) time shows that the problem is fixed-parameter tractable parameterized by the number of terminals. We present fixed-parameter tractable algorithms for Steiner Tree using structurally smaller parameterizations. Our first result concerns the parameterization by a multiway cut S of the terminals, which is a vertex set S (possibly containing terminals) such that each connected component of G-S contains at most one terminal. We show that Steiner Tree can be solved in 2^{𝒪(|S|log|S|)}poly(n) time and polynomial space, where S is a minimum multiway cut for K. The algorithm is based on the insight that, after guessing how an optimal Steiner tree interacts with a multiway cut S, computing a minimum-cost solution of this type can be formulated as minimum-cost bipartite matching. Our second result concerns a new hybrid parameterization called K-free treewidth that simultaneously refines the number of terminals |K| and the treewidth of the input graph. By utilizing recent work on ℋ-Treewidth in order to find a corresponding decomposition of the graph, we give an algorithm that solves Steiner Tree in time 2^{𝒪(k)} poly(n), where k denotes the K-free treewidth of the input graph. To obtain this running time, we show how the rank-based approach for solving Steiner Tree parameterized by treewidth can be extended to work in the setting of K-free treewidth, by exploiting existing algorithms parameterized by |K| to compute the table entries of leaf bags of a tree K-free decomposition. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bart M.P. Jansen and Céline M.F. Swennenhuis 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.76 urn:nbn:de:0030-drops-211471 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.76 eng https://creativecommons.org/licenses/by/4.0/legalcode