论文标题
长路径和单位磁盘图上的循环的道德算法
ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
论文作者
论文摘要
我们为在单位磁盘图上进行了广泛研究的长路径和长周期问题的算法，该算法在时间上运行$ 2^{o（\ sqrt {k}）}（n+m）$。在指数时间假设下，单位磁盘图上的长路径和长周期无法在时间$ 2^{o（\ sqrt {k}）}（n+m）^{o（1）} $ [de berg等人，stoc，stoc 2018]，因此我们的algorithm是最佳的。除了$ 2^{o（\ sqrt {k}）}（n+m）^{o（1）} $ - de Berg等人的（可以说）更简单的顶点封面问题（de Berg等人）的时间算法。 [STOC 2018]（这很容易遵循该问题的$ 2K $ -VERTEX内核），这是UDGS上唯一已知的ETH-ETH-ETH-ETH-tim-Tim-Tim-Tim-practimal固定参数可拖动算法。以前，已知单位磁盘图上的长路径和长周期可在时间内解决$ 2^{o（\ sqrt {k} \ log k）}（n+m）$。该算法涉及引入一种新型的树木分解，需要设计一个非常乏味的动态编程过程。我们的算法基本上更简单：我们完全避免使用这种新型的树木分解。取而代之的是，我们使用标记过程将问题减少到（加权版本的）本身，以宽度$ o（\ sqrt {k}）$的标准树分解。
We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time $2^{O(\sqrt{k})}(n+m)$. Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs cannot be solved in time $2^{o(\sqrt{k})}(n+m)^{O(1)}$ [de Berg et al., STOC 2018], hence our algorithm is optimal. Besides the $2^{O(\sqrt{k})}(n+m)^{O(1)}$-time algorithm for the (arguably) much simpler Vertex Cover problem by de Berg et al. [STOC 2018] (which easily follows from the existence of a $2k$-vertex kernel for the problem), this is the only known ETH-optimal fixed-parameter tractable algorithm on UDGs. Previously, Long Path and Long Cycle on unit disk graphs were only known to be solvable in time $2^{O(\sqrt{k}\log k)}(n+m)$. This algorithm involved the introduction of a new type of a tree decomposition, entailing the design of a very tedious dynamic programming procedure. Our algorithm is substantially simpler: we completely avoid the use of this new type of tree decomposition. Instead, we use a marking procedure to reduce the problem to (a weighted version of) itself on a standard tree decomposition of width $O(\sqrt{k})$.
