License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.44
URN: urn:nbn:de:0030-drops-122024
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12202/
Go to the corresponding LIPIcs Volume Portal

Fomin, Fedor V. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav

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

pdf-format:
LIPIcs-SoCG-2020-44.pdf (0.7 MB)

Abstract

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

BibTeX - Entry

@InProceedings{fomin_et_al:LIPIcs:2020:12202,
  author =	{Fedor V. Fomin and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh and Meirav Zehavi},
  title =	{{ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{44:1--44:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12202},
  URN =		{urn:nbn:de:0030-drops-122024},
  doi =		{10.4230/LIPIcs.SoCG.2020.44},
  annote =	{Keywords: Optimality Program, ETH, Unit Disk Graphs, Parameterized Complexity, Long Path, Long Cycle}
}

Keywords: Optimality Program, ETH, Unit Disk Graphs, Parameterized Complexity, Long Path, Long Cycle
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI