Approximation metatheorems for classes with bounded expansion

DOI10.4230/LIPICS.SWAT.2022.22arXiv2103.08698MaRDI QIDQ6362934

Publication date: 15 March 2021

Abstract: We give a number of approximation metatheorems for monotone maximization problems expressible in the first-order logic, in substantially more general settings than the previously known. We obtain * constant-factor approximation algorithm in any class of graphs with bounded expansion, * a QPTAS in any class with strongly sublinear separators, and * a PTAS in any fractionally treewidth-fragile class (which includes all common classes with strongly sublinear separators. Moreover, our tools also give an exact subexponential-time algorithm in any class with strongly sublinear separators.

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

This page was built for publication: Approximation metatheorems for classes with bounded expansion