ETH-TIGHT ALGORITHMS FOR LONG PATH AND CYCLE ON UNIT DISK GRAPHS∗

Fomin, F.V. and Lokshtanov, D. and Panolan, F. and et al, . (2021) ETH-TIGHT ALGORITHMS FOR LONG PATH AND CYCLE ON UNIT DISK GRAPHS∗. Journal of Computational Geometry, 12 (2). pp. 126-148. ISSN 1920-180X

[img] Text
Computational_Geometry.pdf - Published Version
Restricted to Registered users only

Download (728kB) | Request a copy

Abstract

We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time 2O(√ k) (n+m). Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs cannot be solved in time 2o(√ k) (n + m)O(1) [de Berg et al., STOC 2018], hence our algorithm is optimal. Besides the 2O(√ 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 2O(√k logk) (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(√ k). © 2021, Carleton University. All rights reserved.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Panolan, Fahadhttps://orcid.org/0000-0001-6213-8687
Item Type: Article
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 20 Aug 2022 11:20
Last Modified: 20 Aug 2022 11:20
URI: http://raiith.iith.ac.in/id/eprint/10242
Publisher URL: https://doi.org/10.20382/jocg.v12i2a6
OA policy: https://v2.sherpa.ac.uk/id/publication/27461
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 10242 Statistics for this ePrint Item