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 2O(√ k)nO(1). This improves the 2O(√ klog k)nO(1)-time algorithm by Fomin et al. [SODA 2012, ICALP 2017]. Moreover, our algorithm is optimal assuming the exponential-time hypothesis.
No takes yet. Share an insight, caveat, or question.
An et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: