Nearly ETH-tight algorithms for planar Steiner Tree with terminals on few faces

Sándor Kisfaludi-Bak, Jesper Nederlof, Erik Jan van Leeuwen

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)

Samenvatting

The Steiner Tree problem is one of the most fundamental NP-complete problems as it models many network design problems. Recall that an instance of this problem consists of a graph with edge weights, and a subset of vertices (often called terminals); the goal is to find a subtree of the graph of minimum total weight that connects all terminals. A seminal paper by Erickson et al. [Math. Oper. Res., 1987] considers instances where the underlying graph is planar and all terminals can be covered by the boundary of k faces. Erickson et al. show that the problem can be solved by an algorithm using nO(k) time and nO(k) space, where n denotes the number of vertices of the input graph. In the past 30 years there has been no significant improvement of this algorithm, despite several efforts. In this work, we give an algorithm for Planar Steiner Tree with running time 2O(k)nO(k) using only polynomial space. Furthermore, we show the running time of our algo-rithm is almost tight: we prove that there is no f(k)no(k) algorithm for Planar Steiner Tree for any computable function f, unless the Exponential Time Hypothesis fails.

Originele taal-2Engels
TitelProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
RedacteurenTimothy M. Chan
Plaats van productieNew York
UitgeverijAssociation for Computing Machinery, Inc
Pagina's1015-1034
Aantal pagina's20
ISBN van elektronische versie978-1-61197-548-2
DOI's
StatusGepubliceerd - 2019
Evenement30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, Verenigde Staten van Amerika
Duur: 6 jan 20199 jan 2019

Congres

Congres30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
LandVerenigde Staten van Amerika
StadSan Diego
Periode6/01/199/01/19

Vingerafdruk Duik in de onderzoeksthema's van 'Nearly ETH-tight algorithms for planar Steiner Tree with terminals on few faces'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Kisfaludi-Bak, S., Nederlof, J., & van Leeuwen, E. J. (2019). Nearly ETH-tight algorithms for planar Steiner Tree with terminals on few faces. In T. M. Chan (editor), Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (blz. 1015-1034). Association for Computing Machinery, Inc. https://doi.org/10.1137/1.9781611975482.63