On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs
| Autor: | Michał Pilipczuk, Dániel Marx, Marcin Pilipczuk |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Optimization problem
Parameterized complexity Approximation algorithm 0102 computer and information sciences 02 engineering and technology 01 natural sciences Steiner tree problem Travelling salesman problem Upper and lower bounds Planar graph Combinatorics symbols.namesake 010201 computation theory & mathematics Polynomial kernel TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY 0202 electrical engineering electronic engineering information engineering symbols 020201 artificial intelligence & image processing MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) 2018 IEEE 59th Annual Symposium on Foundations of Computer Science FOCS |
| DOI: | 10.1109/focs.2018.00052 |
| Popis: | There are numerous examples of the so-called "square root phenomenon" in the field of parameterized algorithms: many of the most fundamental graph problems, parameterized by some natural parameter k, become significantly simpler when restricted to planar graphs and in particular the best possible running time is exponential in O(sqrt(k)) instead of O(k) (modulo standard complexity assumptions). We consider two classic optimization problems parameterized by the number of terminals. The Steiner Tree problem asks for a minimum-weight tree connecting a given set of terminals T in an edge-weighted graph. In the Subset Traveling Salesman problem we are asked to visit all the terminals T by a minimum-weight closed walk. We investigate the parameterized complexity of these problems in planar graphs, where the number k = |T| of terminals is regarded as the parameter. Our results are the following: • Subset TSP can be solved in time 2^O(sqrt(k) log k) . n^O(1) even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [SODA 2014] with the same running time that worked only on undirected planar graphs with polynomially large integer weights. • Assuming the Exponential-Time Hypothesis, Steiner Tree on undirected planar graphs cannot be solved in time 2^o(k) . n^O(1), even in the unit-weight setting. This lower bound makes Steiner Tree the first "genuinely planar" problem (i.e., where the input is only planar graph with a set of distinguished terminals) for which we can show that the square root phenomenon does not appear. • Steiner Tree can be solved in time n^O(sqrt(k)) * W on undirected planar graphs with maximum edge weight W. Note that this result is incomparable to the fact that the problem is known to be solvable in time 2^k . n^O(1) even in general graphs. A direct corollary of the combination of our results for Steiner Tree is that this problem does not admit a parameter-preserving polynomial kernel on planar graphs unless ETH fails. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|