I've been stuck with this problem for quite a while now, and after reading so many papers I'm unsure whether this is even possible.

The problem is quite simple:

Given $G = (V, E)$ an undirected graph, find the minimum number of vertices such that their removal from $G$ leaves us with a graph of maximum diameter $2$ (the distance from any two remaining vertices must be at most $2$).

Is it possible to design a constant-factor approximation algorithm for this problem?

My guesses have been to compute $H = (V, E = \{\{u, v\} \mid d_G(u, v) \leq 2\}\} )$ and approximate a clique in $H$, but apparently designing a constant-factor approximation algorithm for $\text{MaxClique}$ is not possible because it is not in $\text{APX}$.

Thank you.

  • $\begingroup$ What is the distance between two of vertices that do not have a path between them? (or, in other words, can the subgraph be disconnected?) $\endgroup$
    – Discrete lizard
    Jun 1, 2023 at 8:48
  • $\begingroup$ @Discretelizard The subgraph cannot be disconnected, the distance would be infinity. $\endgroup$ Jun 1, 2023 at 9:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.