Show simple item record

dc.contributor.authorFomin, Fedor
dc.contributor.authorLokshtanov, Daniel
dc.contributor.authorPanolan, Fahad
dc.contributor.authorSaurabh, Saket
dc.contributor.authorZehavi, Meirav
dc.PublishedLeibniz International Proceedings in Informatics. 2020, 164 .
dc.description.abstractWe 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 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(√k).en_US
dc.publisherSchloss Dagstuhl – Leibniz Center for Informaticsen_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.titleETH-tight algorithms for long path and cycle on unit disk graphsen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.rights.holderCopyright the authorsen_US
dc.source.journalLeibniz International Proceedings in Informaticsen_US
dc.relation.projectNorges forskningsråd: 263317en_US
dc.identifier.citationIn: Cabello, S. and Chen, D. Z. (eds.), 36th International Symposium on Computational Geometry (SoCG 2020), 44.en_US
dc.source.volumeSoCG 2020en_US

Files in this item


This item appears in the following Collection(s)

Show simple item record

Navngivelse 4.0 Internasjonal
Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal