Approximating 2-cliques in unit disk graphs

This paper studies distance-based clique relaxations in unit disk graphs arising in wireless networking applications. Namely, a 2-clique is a subset of nodes with pairwise distance at most two in the graph, and a 2-club is a subset of nodes inducing a subgraph of diameter two. It is shown that in a unit disk graph any 2-clique is 4-dominated and any 2-club is 3-dominated. The former observation is used to develop a 1 2 -approximation algorithm for the maximum 2-clique problem in unit disk graphs. Moreover, this also implies polynomial solvability of the minimum dominating set problem in unit disk graphs of diameter two, whereas the same problem is shown to be hard in general diameter-two graphs. The paper also poses several related open questions of interest.