2026-07-22T14:20:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12202 2024-03-06T10:49:41Z ddc:004 open_access

ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs Fomin, Fedor V. Lokshtanov, Daniel Panolan, Fahad Saurabh, Saket Zehavi, Meirav Optimality Program ETH Unit Disk Graphs Parameterized Complexity Long Path Long Cycle We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time 2^{𝒪(√k)}(n+m). Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs cannot be solved in time 2^{o(√k)}(n+m)^𝒪(1) [de Berg et al., STOC 2018], hence our algorithm is optimal. Besides the 2^{𝒪(√k)}(n+m)^𝒪(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^{𝒪(√klog 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 𝒪(√k). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh and Meirav Zehavi 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.44 urn:nbn:de:0030-drops-122024 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.44 eng https://creativecommons.org/licenses/by/3.0/legalcode