Approximation algorithms for polynomial-expansion and low-density graphs

Sariel Har-Peled, Kent Quanrud

Research output: Contribution to journalArticle

Abstract

We investigate the family of intersection graphs of low density objects in low dimensional Euclidean space. This family is quite general, includes planar graphs, and in particular is a subset of the family of graphs that have polynomial expansion. We present efficient (1+)-approximation algorithms for polynomial expansion graphs for unweighted Independent Set, Set Cover, and Dominating Set problems, among others, and these results seem to be new. Naturally, PTASs for these problems are known for subclasses of this graph family. These results have immediate applications in the geometric domain. For example, the new algorithms yield the only PTAS known for covering points by fat triangles (that are shallow). We also prove corresponding hardness of approximation for some of these optimization problems, characterizing their intractability with respect to density. For example, we show that there is no PTAS for covering points by fat triangles if they are not shallow, thus matching our PTAS for this problem with respect to depth.

Original languageEnglish (US)
Pages (from-to)1712-1744
Number of pages33
JournalSIAM Journal on Computing
Volume46
Issue number6
DOIs
StatePublished - Jan 1 2017

Keywords

  • Independent set
  • PTAS
  • Polynomial expansion
  • SETH
  • Separators

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Approximation algorithms for polynomial-expansion and low-density graphs'. Together they form a unique fingerprint.

  • Cite this