ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
<|reference_start|>ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs: In this paper, we consider the Cycle Packing problem on unit disk graphs 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(\sqrt k)}n^{O(1)}$. This improves the $2^{O(\sqrt k\log k)}n^{O(1)}$-time algorithm by Fomin et al. [SODA 2012, ICALP 2017]. Moreover, our algorithm is optimal assuming the exponential-time hypothesis.<|reference_end|>
@article{an2024eth-tight,
    title={ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs},
    author={Shinwoo An and Eunjin Oh},
    journal={arXiv preprint arXiv:2403.11426},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.11426},
    primaryClass={cs.DS cs.CG}
}