PTAS for H-free node deletion problems in disk graphs

For a set H of graphs, a graph G is H-free if G does not contain any subgraph isomorphic to some graph in H. In this paper, we study the minimum H-free node deletion problem (MinHFND) and the maximum H-free node set problem (MaxHNS), which include a lot of extensively-studied problems such as the minimum k-path vertex cover problem, the dissociation number problem, and the minimum degree bounded node deletion problem. For a large class of H, PTASs are given for MinHFND and MaxHFNS on disk graphs whose heterogeneity is bounded by a constant, where the heterogeneity of a disk graph is the ratio of the maximum radius to the minimum radius of disks. (C) 2018 Elsevier B.V. All rights reserved.