Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs

DOI10.1007/978-3-662-48350-3_60MaRDI QIDQ3452835zbMATH OpenOpenAlexFDO

Authors Kent Quanrud, Sariel Har-Peled

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

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

zbMATH Keywords

computational geometryhardness of approximationSETH

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Abstract: We study the family of intersection graphs of low density objects in low dimensional Euclidean space. This family is quite general, and includes planar graphs. We prove that such graphs have small separators. Next, we present efficient $(1+varepsilon)$-approximation algorithms for these graphs, for Independent Set, Set Cover, and Dominating Set problems, among others. We also prove corresponding hardness of approximation for some of these optimization problems, providing a characterization of their intractability in terms of density.

Recommendations

• Approximation algorithms for polynomial-expansion and low-density graphs
• Approximation algorithms for graph approximation problems
• Polynomial-time approximation schemes for geometric graphs
• Algorithms for classes of graphs with bounded expansion
• Approximation algorithms for approximating graphs with bounded number of connected components
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Approximation algorithms for finding low-degree subgraphs
• Subexponential parameterized algorithms for graphs of polynomial growth
• Sublinear graph approximation algorithms

Cites work

• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation algorithms for polynomial-expansion and low-density graphs
• Covering a ball with smaller equal balls in R^n
• Diameter and treewidth in minor-closed graph families
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Faster shortest-path algorithms for planar graphs
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Improved approximation algorithms for geometric set cover
• Improved bounds for the union of locally fat objects in the plane
• Improved results on geometric hitting set problems
• Local tree-width, excluded minors, and approximation algorithms
• Motion planning in environments with low obstacle density
• Near-optimal separators in string graphs
• ON CONVEX POLYHEDRA IN LOBAČEVSKIĬ SPACES
• Polynomial-time approximation schemes for packing and piercing fat objects
• Quasi-polynomial time approximation scheme for sparse subsets of polygons
• Separators for sphere-packings and nearest neighbor graphs
• Simple PTAS's for families of graphs excluding a minor
• Small-size -nets for axis-parallel rectangles and boxes
• Sparsity. Graphs, structures, and algorithms
• State of the union (of geometric objects)
• The complexity of the free space for motion planning amidst fat obstacles

Cited in

(18)

• Stable approximation algorithms for dominating set and independent set
• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• Lossy kernels for connected dominating set on sparse graphs
• Approximation algorithms for polynomial-expansion and low-density graphs
• A tight analysis of geometric local search
• scientific article; zbMATH DE number 7378687 (Why is no real title available?)
• Packing and covering with non-piercing regions
• Lossy kernels for connected dominating set on sparse graphs
• Subexponential parameterized algorithms for graphs of polynomial growth
• Hardness of the generalized coloring numbers
• Optimality of geometric local search
• On the size of outer-string representations
• Parameterized complexity of geometric covering problems having conflicts
• Sublinear separators in intersection graphs of convex shapes
• Distributed Dominating Set Approximations beyond Planar Graphs
• An annotated bibliography on 1-planarity
• Local search is a PTAS for feedback vertex set in minor-free graphs
• Computational complexity for the problem of optimal intersection of straight line segments by disks

This page was built for publication: Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs

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