Bhore, Sujoy ;
Carmi, Paz ;
Kolay, Sudeshna ;
Zehavi, Meirav
Parameterized Study of Steiner Tree on Unit Disk Graphs
Abstract
We study the Steiner Tree problem on unit disk graphs. Given a n vertex unit disk graph G, a subset R⊆ 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 NPhard. Next, we prove that the Steiner Tree problem on unit disk graphs can be solved in n^{O(√{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 cliquegrid 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.
BibTeX  Entry
@InProceedings{bhore_et_al:LIPIcs:2020:12260,
author = {Sujoy Bhore and Paz Carmi and Sudeshna Kolay and Meirav Zehavi},
title = {{Parameterized Study of Steiner Tree on Unit Disk Graphs}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {13:113:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771504},
ISSN = {18688969},
year = {2020},
volume = {162},
editor = {Susanne Albers},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12260},
URN = {urn:nbn:de:0030drops122607},
doi = {10.4230/LIPIcs.SWAT.2020.13},
annote = {Keywords: Unit Disk Graphs, FPT, Subexponential exact algorithms, NPHardness, WHardness}
}
12.06.2020
Keywords: 

Unit Disk Graphs, FPT, Subexponential exact algorithms, NPHardness, WHardness 
Seminar: 

17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Issue date: 

2020 
Date of publication: 

12.06.2020 