## Abstract

The MAXIMUM INDEPENDENT SET problem in

*d*-box graphs, i.e., in the intersection graphs of axis-parallel rectangles in R^{d}, is a challenge open problem. For any fixed*d*≥ 2 the problem is NP-hard and no approximation algorithm with ratio*o*(log*-*^{d}^{1}*n*) is known. In some restricted cases, e.g., for*d*-boxes with bounded aspect ratio, a PTAS exists [17]. In this paper we prove APX-hardness (and hence non-existence of a PTAS, unless P = NP), of the MAXIMUM INDEPENDENT SET problem in*d*-box graphs for any fixed*d*≥ 3. We state also first explicit lower bound 443/442 on efficient approximability in such case. Additionally, we provide a generic method how to prove APX-hardness for many NP-hard graph optimization problems in*d*-box graphs for any fixed*d*≥ 3. In 2-dimensional case we give a generic approach to NP-hardness results for these problems in highly restricted intersection graphs of axis-parallel unit squares (alternatively, in unit disk graphs).Original language | English |
---|---|

Title of host publication | SODA '05 Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms |

Place of Publication | Philadelphia |

Publisher | Society for Industrial and Applied Mathematics |

Pages | 267-276 |

ISBN (Print) | 9780898715859 |

Publication status | Published - 2005 |