Publication at Faculty of Mathematics and Physics |
2022
Abstract
We give a number of approximation metatheorems for monotone maximization problems expressible in the first-order logic, in substantially more general settings than previously known. We obtain a 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.