# Constant factor approximation algorithm for Vertex Deletion version of Maximum Diameter Bounded Subgraph

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.

• 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?) Jun 1, 2023 at 8:48
• @Discretelizard The subgraph cannot be disconnected, the distance would be infinity. Jun 1, 2023 at 9:15