Improved (In-)Approximability Bounds for d-Scattered Set
Vol. 27, no. 3, pp. 219-238, 2023. Regular paper.
Abstract In the $d$-${\rm S{\small CATTERED}\;S{\small ET}}$ problem we are asked to select at least $k$ vertices of a given graph, so that the distance between any pair is at least $d$. We study the problem's (in-)approximability and offer improvements and extensions of known results for ${\rm I{\small NDEPENDENT}\;S{\small ET}}$, of which it is a generalization. Specifically, we show:
  • A lower bound of $\Delta^{\lfloor d/2\rfloor-\epsilon}$ on the approximation ratio of any polynomial-time algorithm for graphs of maximum degree $\Delta$ and an improved upper bound of $O(\Delta^{\lfloor d/2\rfloor})$ on the approximation ratio of any greedy scheme for this problem.
  • A polynomial-time $2\sqrt{n}$-approximation for bipartite graphs and even values of $d$, that matches the known lower bound by considering the only remaining case.
  • A lower bound on the complexity of any $\rho$-approximation algorithm of (roughly) $2^{\frac{n^{1-\epsilon}}{\rho d}}$ for even $d$ and $2^{\frac{n^{1-\epsilon}}{\rho(d+\rho)}}$ for odd $d$ (under the randomized ETH), complemented by $\rho$-approximation algorithms of running-times that (almost) match these bounds.

 This work is licensed under the terms of the CC-BY license.
Submitted: June 2020.
Reviewed: February 2021.
Revised: February 2021.
Accepted: April 2023.
Final: April 2023.
Published: May 2023.
Communicated by Guy Even
article (PDF)