Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs
Karim Abu-Affash
Shamoon College of Engineering

We consider a well studied generalization of the maximum clique problem which is defined as follows. Given a graph $G$ on $n$ vertices and a fixed parameter $d\geq 1$, in the maximum diameter-bounded subgraph problem (MaxDBS for short), the goal is find a (vertex) maximum subgraph of $G$ of diameter at most $d$.

In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor 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 VC-dimension, $k$-quasi planar graphs, fractional Helly theorems and several geometric properties of unit disk graphs.