ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs

Abstract

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})$.

arXiv commentExtended version to appear in SoCG'20