arXiv preprint ·
Steiner Tree Parameterized by Multiway Cut: Single-Exponential Time and Polynomial Space
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In the Steiner Tree problem, the goal is to find a minimum-weight tree containing a given set of terminals in an edge-weighted graph. Given a multiway cut of size $s$, we propose a deterministic algorithm running in $2^{O(s)}\operatorname{poly}(n,b)$ time and polynomial space ($n$ vertices, non-negative $b$-bit integer weights). A multiway cut for the terminals is a set of vertices whose deletion leaves at most one terminal in each connected component. This result answers a question of Jansen and Swennenhuis (ESA 2024). Building on their component decomposition, we show that it suffices to connect the selected cut vertices together with $O(s)$ additional terminals and attach the remaining terminals by shortest paths. We use colour coding to optimize over the choice of these additional terminals.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than $1-1/e$
Limits and Constants of OpenAI's Claimed ETH Refutation
Traveling Salesman Problem on Graphs with Proportional Independent Set
Facility Location with Customer Incompatibilities
Multiple Swap Local Search Approximations for Uniform-Cost Capacitated Facility Location with Extensions to Outliers
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.