Approximation Metatheorems for Classes with Bounded Expansion

Abstrakt

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.

Klíčová slova

• approximation
• bounded expansion
• meta-algorithms