The Library
Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
Tools
Dvořák, Pavel, Feldmann, Andreas Emil, Knop, Dušan, Masařík, Tomáš, Toufar, Tomáš and Veselý, Pavel (2021) Parameterized approximation schemes for Steiner trees with small number of Steiner vertices. SIAM Journal on Discrete Mathematics, 35 (1). pp. 546-574. doi:10.1137/18M1209489 ISSN 0895-4801.
|
PDF
WRAP-parameterized-approximation-schemes-Steiner-trees-small-number-Steiner vertices-Veselý-2020.pdf - Accepted Version - Requires a PDF viewer. Download (1052Kb) | Preview |
Official URL: https://doi.org/10.1137/18M1209489
Abstract
We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of approximation and also parameterization. In particular, on one hand Steiner Tree is known to be ${APX}$-hard, and ${W[2]}$-hard on the other, if parameterized by the number of nonterminals (Steiner vertices) in the optimum solution. In contrast to this, we give an efficient parameterized approximation scheme (${EPAS}$), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (${PSAKS}$) for the considered parameter. We further study the parameterized approximability of other variants of Steiner Tree, such as Directed Steiner Tree and Steiner Forest. For none of these is an ${EPAS}$ likely to exist for the studied parameter. For Steiner Forest an easy observation shows that the problem is ${APX}$-hard, even if the input graph contains no Steiner vertices. For Directed Steiner Tree we prove that approximating within any function of the studied parameter is ${W[1]}$-hard. Nevertheless, we show that an ${EPAS}$ exists for Unweighted Directed Steiner Tree, but a ${PSAKS}$ does not. We also prove that there is an ${EPAS}$ and a ${PSAKS}$ for Steiner Forest if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter.
Item Type: | Journal Article | ||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Alternative Title: | |||||||||||||||||||||||||||||||
Subjects: | Q Science > QA Mathematics | ||||||||||||||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Steiner systems, Graph theory, Approximation algorithms | ||||||||||||||||||||||||||||||
Journal or Publication Title: | SIAM Journal on Discrete Mathematics | ||||||||||||||||||||||||||||||
Publisher: | Society for Industrial and Applied Mathematics | ||||||||||||||||||||||||||||||
ISSN: | 0895-4801 | ||||||||||||||||||||||||||||||
Official Date: | 28 March 2021 | ||||||||||||||||||||||||||||||
Dates: |
|
||||||||||||||||||||||||||||||
Volume: | 35 | ||||||||||||||||||||||||||||||
Number: | 1 | ||||||||||||||||||||||||||||||
Page Range: | pp. 546-574 | ||||||||||||||||||||||||||||||
DOI: | 10.1137/18M1209489 | ||||||||||||||||||||||||||||||
Status: | Peer Reviewed | ||||||||||||||||||||||||||||||
Publication Status: | Published | ||||||||||||||||||||||||||||||
Reuse Statement (publisher, data, author rights): | First Published in SIAM Journal on Discrete Mathematics in 35(1), published by the Society for Industrial and Applied Mathematics (SIAM) Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. | ||||||||||||||||||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||||||||||||||
Copyright Holders: | © 2021, Society for Industrial and Applied Mathematics | ||||||||||||||||||||||||||||||
Date of first compliant deposit: | 17 November 2020 | ||||||||||||||||||||||||||||||
Date of first compliant Open Access: | 19 April 2021 | ||||||||||||||||||||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||||||||||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year