文章基本信息

标题：Parameterized Study of Steiner Tree on Unit Disk Graphs
本地全文：下载
作者：Sujoy Bhore ; Paz Carmi ; Sudeshna Kolay 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：162
页码：13:1-13:18
DOI：10.4230/LIPIcs.SWAT.2020.13
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study the Steiner Tree problem on unit disk graphs. Given a n vertex unit disk graph G, a subset RâS V(G) of t vertices and a positive integer k, the objective is to decide if there exists a tree T in G that spans over all vertices of R and uses at most k vertices from Vâ§µ R. The vertices of R are referred to as terminals and the vertices of V(G)â§µ R as Steiner vertices. First, we show that the problem is NP-hard. Next, we prove that the Steiner Tree problem on unit disk graphs can be solved in n^{O(â^S{t+k})} time. We also show that the Steiner Tree problem on unit disk graphs parameterized by k has an FPT algorithm with running time 2^{O(k)}n^{O(1)}. In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs [Fomin et al., 2019]. We mention that the algorithmic results can be made to work for Steiner Tree on disk graphs with bounded aspect ratio. Finally, we prove that Steiner Tree on disk graphs parameterized by k is W[1]-hard.
关键词：Unit Disk Graphs; FPT; Subexponential exact algorithms; NP-Hardness; W-Hardness