ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs

Abstract

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.

arXiv commentIn SoCG'24