AbuAffash, A. Karim ;
Carmi, Paz ;
Maheshwari, Anil ;
Morin, Pat ;
Smid, Michiel ;
Smorodinsky, Shakhar
Approximating Maximum DiameterBounded Subgraph in Unit Disk Graphs
Abstract
We consider a well studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and an integer d >= 1, in the maximum diameterbounded subgraph problem (MaxDBS for short), the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d=1, this problem is equivalent to the maximum clique problem and thus it is NPhard to approximate it within a factor n^{1epsilon}, for any epsilon > 0. Moreover, it is known that, for any d >= 2, it is NPhard to approximate MaxDBS within a factor n^{1/2  epsilon}, for any epsilon > 0.
In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomialtime constantfactor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VCdimension, kquasi planar graphs, fractional Helly theorems and several geometric properties of unit disk graphs.
BibTeX  Entry
@InProceedings{abuaffash_et_al:LIPIcs:2018:8715,
author = {A. Karim AbuAffash and Paz Carmi and Anil Maheshwari and Pat Morin and Michiel Smid and Shakhar Smorodinsky},
title = {{Approximating Maximum DiameterBounded Subgraph in Unit Disk Graphs}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {2:12:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770668},
ISSN = {18688969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8715},
URN = {urn:nbn:de:0030drops87152},
doi = {10.4230/LIPIcs.SoCG.2018.2},
annote = {Keywords: Approximation algorithms, maximum diameterbounded subgraph, unit disk graphs, fractional Helly theorem, VCdimension}
}
08.06.2018
Keywords: 

Approximation algorithms, maximum diameterbounded subgraph, unit disk graphs, fractional Helly theorem, VCdimension 
Seminar: 

34th International Symposium on Computational Geometry (SoCG 2018)

Issue date: 

2018 
Date of publication: 

08.06.2018 