### 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 language | English (US) |
---|---|

Pages (from-to) | 1712-1744 |

Number of pages | 33 |

Journal | SIAM Journal on Computing |

Volume | 46 |

Issue number | 6 |

DOIs | |

State | Published - 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

*SIAM Journal on Computing*,

*46*(6), 1712-1744. https://doi.org/10.1137/16M1079336