Steiner Tree Parameterized by Multiway Cut and Even Less
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909233043210240 |
|---|---|
| author | Jansen, Bart M. P. Swennenhuis, Céline M. F. |
| author_facet | Jansen, Bart M. P. Swennenhuis, Céline M. F. |
| contents | 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|} \mathsf{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^{O(|S|\log|S|)}\mathsf{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 $\mathcal{H}$-Treewidth in order to find a corresponding decomposition of the graph, we give an algorithm that solves Steiner Tree in time $2^{O(k)} \mathsf{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_19819 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Steiner Tree Parameterized by Multiway Cut and Even Less Jansen, Bart M. P. Swennenhuis, Céline M. F. Data Structures and Algorithms 05C85, 68Q27 F.2.2 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|} \mathsf{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^{O(|S|\log|S|)}\mathsf{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 $\mathcal{H}$-Treewidth in order to find a corresponding decomposition of the graph, we give an algorithm that solves Steiner Tree in time $2^{O(k)} \mathsf{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. |
| title | Steiner Tree Parameterized by Multiway Cut and Even Less |
| topic | Data Structures and Algorithms 05C85, 68Q27 F.2.2 |
| url | https://arxiv.org/abs/2406.19819 |