On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs
On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs
复制标题
平面图上Steiner树和有向子集TSP的次指数参数化算法
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Michal Pilipczuk
中科院分区：
文献类型：
--
作者：
D. Marx;Marcin Pilipczuk;Michal Pilipczuk
在参数化算法领域有许多所谓的“平方根现象”的例子：许多最基本的图问题，由一些自然参数k参数化，当限制到平面图时变得明显更简单，特别是最好的可能运行时间是指数O（sqrt（k））而不是O（k）（模标准复杂度假设）。我们考虑两个经典的优化问题参数终端的数量。Steiner树问题要求在边加权图中连接给定终端集合T的最小权树。在子集旅行商问题中，我们被要求通过最小权闭行走访问所有终端T。我们研究了平面图中这些问题的参数化复杂性，其中k =|不|终端数作为参数。我们的结果如下：·子集TSP可以在2^O（sqrt（k）log k）的时间内求解。n^O（1），甚至在边权有向平面图上。这改进了Klein和马克思[SODA 2014]的算法，其运行时间相同，仅适用于具有多项式大整数权重的无向平面图。·假设指数时间假设，无向平面图上的Steiner树不能在时间2^o（k）内求解。n^O（1），即使在单位权重设置下。这个下界使得斯坦纳树成为第一个“真正平面”问题（即，其中输入仅是具有一组可区分终端的平面图），对于该平面图，我们可以证明平方根现象不会出现。· Steiner树可以在具有最大边权重W的无向平面图上在时间n^O（sqrt（k））* W内求解。请注意，这个结果与已知问题在时间2^k内可解的事实是不可比较的。n^O（1），甚至在一般图中。一个直接的推论，我们的结果相结合的Steiner树是，这个问题不承认一个参数保持多项式核平面图，除非ETH失败。
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.