2026-07-21T12:47:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19952 2024-06-06T06:21:13Z ddc:004 open_access

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs An, Shinwoo Oh, Eunjin Unit disk graphs cycle packing tree decomposition parameterized algorithm In this paper, we consider the Cycle Packing problem on a unit disk graph defined as follows. Given a unit disk graph G with n vertices and an integer k, the goal is to find a set of k vertex-disjoint cycles of G if it exists. Our algorithm runs in time 2^O(√k) n^O(1). This improves the 2^O(√klog k) n^O(1)-time algorithm by Fomin et al. [SODA 2012, ICALP 2017]. Moreover, our algorithm is optimal assuming the exponential-time hypothesis. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shinwoo An and Eunjin Oh 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.7 urn:nbn:de:0030-drops-199522 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.7 eng https://creativecommons.org/licenses/by/4.0/legalcode