Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs.

In this paper, we study the minimum (connected) k -bounded-degree node deletion problem (Min(C) k BDND). For a connected graph G , a constant k and a weight function w : V → R + , a vertex set C ⊆ V (G) is a k BDND-set if the maximum degree of graph G − C is at most k. If furthermore, the subgraph of G induced by C is connected, then C is a C k BDND-set. The goal of MinW k BDND (resp. MinWC k BDND) is to find a k BDND-set (resp. C k BDND-set) with the minimum weight. In this paper, we focus on their cardinality versions with w (v) ≡ 1 , v ∈ V , which are denoted as Min k BDND and MinC k BDND. This paper presents a (1 + ε) and a 3.76-approximation algorithm for Min k BDND and MinC k BDND on unit disk graphs, respectively, where 0 < ε < 1 is an arbitrary constant. [ABSTRACT FROM AUTHOR]