Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes

Miroslav Chlebik, Janka Chlebikova

Research output: Chapter in Book/Report/Conference proceedingConference contribution

60 Downloads (Pure)

Abstract

The MAXIMUM INDEPENDENT SET problem in d-box graphs, i.e., in the intersection graphs of axis-parallel rectangles in Rd, is a challenge open problem. For any fixed d ≥ 2 the problem is NP-hard and no approximation algorithm with ratio o(logd-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 languageEnglish
Title of host publicationSODA '05 Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms
Place of PublicationPhiladelphia
PublisherSociety for Industrial and Applied Mathematics
Pages267-276
ISBN (Print)9780898715859
Publication statusPublished - 2005

Fingerprint

Dive into the research topics of 'Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes'. Together they form a unique fingerprint.

Cite this