A Framework for Approximation Schemes on Disk Graphs

Abstract

We initiate a systematic study of approximation schemes for fundamental optimization problems on disk graphs, a common generalization of both planar graphs and unit-disk graphs. Our main contribution is a general framework for designing efficient polynomial-time approximation schemes (EPTASes) for vertex- deletion problems on disk graphs, which results in EPTASes for many fundamental problems including VERTEX COVER, FEEDBACK VERTEX SET, SMALL CYCLE HITTING (in particular, TRIANGLE HITTING), Pk-VERTEX DELETION for k ∈ {3,4,5}, PATH DELETION, PATHWIDTH 1-DELETION, COMPONENT ORDER CONNECTIVITY, BOUNDED DEGREE DELETION, PSEUDOFOREST DELETION, FINITE-TYPE COMPONENT DELETION, etc. All EPTASes obtained using our framework are robust in the sense that they do not require a realization of the input disk graph (in fact, we allow the input to be any graph, and our algorithms either output a correct approximation solution for the problem or conclude that the input graph is not a disk graph). To the best of our knowledge, prior to this work, the only problems known to admit PTASes or EPTASes on disk graphs are MAXIMUM CLIQUE, INDEPENDENT SET, DOMINATING SET, and VERTEX COVER, among which the existing PTAS [Erlebach et al., SICOMP'05] and EPTAS [Leeuwen, SWAT'06] for VERTEX COVER require a realization of the input disk graph (while ours does not).The core of our framework is a reduction for a broad class of (approximation) vertex-deletion problems from (general) disk graphs to disk graphs of bounded local radius, which is a new invariant of disk graphs introduced in this work. Disk graphs of bounded local radius can be viewed as a "mild" generalization of planar graphs, which preserves certain nice properties of planar graphs. Specifically, we prove that disk graphs of bounded local radius admit the Excluded Grid Minor property and have locally bounded treewidth. This allows existing techniques for designing approximation schemes on planar graphs (e.g., bidimensionality and Baker's technique) to be directly applied to disk graphs of bounded local radius.* The full version of the paper can be accessed at https://arxiv.org/abs/2211.02717

Locations

• arXiv (Cornell University) - View - PDF
• Society for Industrial and Applied Mathematics eBooks - View