Thin graph classes and polynomial-time approximation schemes

MaRDI QIDQ4607999zbMATH OpenFDO

Authors Zdeněk Dvořák

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1704.00125, http://dl.acm.org/citation.cfm?id=3175415

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: Baker devised a powerful technique to obtain approximation schemes for various problems restricted to planar graphs. Her technique can be directly extended to various other graph classes, among the most general ones the graphs avoiding a fixed apex graph as a minor. Further generalizations (e.g., to all proper minor closed graph classes) are known, but they use a combination of techniques and usually focus on somewhat restricted classes of problems. We present a new type of graph decompositions (thin systems of overlays) generalizing Baker's technique and leading to straightforward polynomial-time approximation schemes. We also show that many graph classes (all proper minor-closed classes, and all subgraph-closed classes with bounded maximum degree and strongly sublinear separators) admit such decompositions.

Recommendations

• Excluded grid minors and efficient polynomial-time approximation schemes
• Approximation algorithms for NP-complete problems on planar graphs
• Efficient Approximation Schemes for Maximization Problems onK3,3-free orK5-free Graphs
• Faster approximation schemes and parameterized algorithms on H-minor-free and odd-minor-free graphs
• Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs

Cited in

(7)

• Layered separators in minor-closed graph classes with applications
• Thinning Algorithms as Multivalued ${\mathcal{N}}$ -Retractions
• Polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graphs
• Greedy spanners in Euclidean spaces admit sublinear separators
• Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
• Pliability and approximating Max-CSPs
• Robust contraction decomposition for minor-free graphs and its applications

This page was built for publication: Thin graph classes and polynomial-time approximation schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607999)