dc.contributor.author | Fomin, Fedor | |
dc.contributor.author | Lokshtanov, Daniel | |
dc.contributor.author | Panolan, Fahad | |
dc.contributor.author | Saurabh, Saket | |
dc.contributor.author | Zehavi, Meirav | |
dc.date.accessioned | 2021-07-06T13:15:46Z | |
dc.date.available | 2021-07-06T13:15:46Z | |
dc.date.created | 2020-07-02T10:33:22Z | |
dc.date.issued | 2020 | |
dc.Published | Leibniz International Proceedings in Informatics. 2020, 164 . | |
dc.identifier.isbn | 978-3-95977-143-6 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/2763608 | |
dc.description.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 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.language.iso | eng | en_US |
dc.publisher | Schloss Dagstuhl – Leibniz Center for Informatics | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | ETH-tight algorithms for long path and cycle on unit disk graphs | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright the authors | en_US |
dc.source.articlenumber | 44 | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.4230/LIPIcs.SoCG.2020.44 | |
dc.identifier.cristin | 1818234 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.40 | 164 | |
dc.relation.project | Norges forskningsråd: 263317 | en_US |
dc.identifier.citation | In: Cabello, S. and Chen, D. Z. (eds.), 36th International Symposium on Computational Geometry (SoCG 2020), 44. | en_US |
dc.source.volume | SoCG 2020 | en_US |