PTAS for minimum k-path vertex cover in ball graph

A vertex set F is a k-path vertex cover (VCPk) of graph G if every path of G on k vertices contains at least one vertex from F. A graph G is a d-dimensional ball graph if each vertex of G corresponds to a ball in Rd, two vertices are adjacent in G if and only if their corresponding balls have nonempty intersection. The heterogeneity of a ball graph is defined to be rmax/rmin, where rmax and rmin are the largest radius and the smallest radius of those balls, respectively. In this paper, we present a PTAS for the minimum VCPk problem in a ball graph whose heterogeneity is bounded by a constant.