Paper Info
Title
Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
Abstract
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) with the above parameterization, using only polynomial space. Furthermore, we show that the running time of our algorithm 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.
Year
DOI
Venue
2020
10.1145/3371389
ACM Transactions on Algorithms
Keywords
DocType
Volume
Planar graphs,Steiner tree,exact algorithms,exponential time hypothesis,lower bound,parameterized algorithms
Journal
16
Issue
ISSN
Citations 
3
1549-6325
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Sándor Kisfaludi-Bak159.21
Jesper Nederlof229424.22
Erik Jan van Leeuwen327525.89