[Back]

S. Bhore, P. Carmi, S. Kolay, M. Zehavi:
"Parameterized Study of Steiner Tree on Unit DiskGraphs";
Talk: Symposium and Workshops on Algorithm Theory (SWAT), Torshavn, Faroe Islands; 2020-06-22 - 2020-06-24; in: "17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)", LIPICS, 162 (2020), ISBN: 978-3-95977-150-4; 1 - 18.

We study theSteiner Treeproblem on unit disk graphs. Given anvertex unit disk graphG, asubsetR⊆V(G)oftvertices and a positive integerk, the objective is to decide if there exists atreeTinGthat spans over all vertices ofRand uses at mostkvertices fromV\R. The verticesofRare referred to asterminalsand the vertices ofV(G)\RasSteinervertices. First, we showthat the problem isNP-hard. Next, we prove that theSteiner Treeproblem on unit disk graphscan be solved innO(√t+k)time. We also show that theSteiner Treeproblem on unit disk graphsparameterized bykhas an FPT algorithm with running time2O(k)nO(1). In fact, the algorithmsare designed for a more general class of graphs, called clique-grid graphs [16]. We mention that thealgorithmic results can be made to work forSteiner Treeon disk graphs with bounded aspectratio. Finally, we prove thatSteiner Treeon disk graphs parameterized bykis W[1]-hard.

http://dx.doi.org/10.4230/LIPIcs.SWAT.2020.13

https://publik.tuwien.ac.at/files/publik_293821.pdf