Simple PTAS's for families of graphs excluding a minor

DOI10.1016/J.DAM.2015.03.004MaRDI QIDQ2352263zbMATH OpenOpenAlexFDO

Authors S. Cabello, David Gajser

Publication date 30 June 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.5778

zbMATH Keywords

forbidden minorlocal optimizationmaximum independent setminimum dominating setminimum vertex coverpolynomial-time approximation schemeseparator

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph minors (05C83)

Abstract: We show that very simple algorithms based on local search are polynomial-time approximation schemes for Maximum Independent Set, Minimum Vertex Cover and Minimum Dominating Set, when the input graphs have a fixed forbidden minor.

Recommendations

• Local tree-width, excluded minors, and approximation algorithms
• Local search is a PTAS for feedback vertex set in minor-free graphs
• Distributed Almost Exact Approximations for Minor-Closed Families
• Excluded grid minors and efficient polynomial-time approximation schemes
• Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs

Cites work

• A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
• Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation algorithms for NP-complete problems on planar graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Graph minors. XVI: Excluding a non-planar graph
• Guarding terrains via local search
• Improved local search for geometric hitting set
• Improved results on geometric hitting set problems
• Independent set of intersection graphs of convex objects in 2D
• Local tree-width, excluded minors, and approximation algorithms
• Single source shortest paths in H-minor free graphs

Cited in

(15)

• A tight analysis of geometric local search
• Local search is a PTAS for feedback vertex set in minor-free graphs
• Constructing planar support for non-piercing regions
• A simple local search gives a PTAS for the Feedback Vertex Set problem in minor-free graphs
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
• LP-based robust algorithms for noisy minor-free and bounded treewidth graphs
• Approximation algorithms for polynomial-expansion and low-density graphs
• A local-search algorithm for Steiner forest
• scientific article; zbMATH DE number 7378687 (Why is no real title available?)
• Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
• Optimality of geometric local search
• Limits of local search: quality and efficiency
• Computing connected-k-subgraph cover with connectivity requirement
• Greedy spanners in Euclidean spaces admit sublinear separators

This page was built for publication: Simple PTAS's for families of graphs excluding a minor

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