In this paper, we present an algorithm for computing a feedback vertex set of a unit disk graph of size $k$, if it exists, which runs in time $2^{ O(\sqrt{ k})}(n+m)$, where $n$ and $m$ denote the numbers of vertices and edges, respectively. This improves the $2^{ O(\sqrt{ k}\log k)}n^{ O(1)}$-time algorithm for this problem on unit disk graphs by Fomin et al. [ICALP 2017]. Moreover, our algorithm is optimal assuming the exponential-time hypothesis. Also, our algorithm can be extended to handle geometric intersection graphs of similarly sized fat objects without increasing the running time.
Categories: cs.CG