Parameterized Study of Steiner Tree on Unit Disk Graphs
| Autor: | Sujoy Bhore, Paz Carmi, Sudeshna Kolay, Meirav Zehavi |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Subexponential exact algorithms
Computational Geometry (cs.CG) FOS: Computer and information sciences General Computer Science Unit Disk Graphs Applied Mathematics FPT TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY W-Hardness Computer Science - Computational Geometry NP-Hardness Computer Science Applications MathematicsofComputing_DISCRETEMATHEMATICS |
| Popis: | We study the Steiner Tree problem on unit disk graphs. Given a $n$ vertex unit disk graph $G$, a subset $R\subseteq 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\setminus R$. The vertices of $R$ are referred to as terminals and the vertices of $V(G)\setminus 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(\sqrt{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. We mention that the algorithmic results can be made to work for the Steiner Tree on disk graphs with bounded aspect ratio. Finally, we prove that the Steiner Tree on disk graphs parameterized by $k$ is W[1]-hard. Accepted in Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) 2020 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|