# k-center 2.0: A stronger k-center condition

Given an unweighted, undirected graph, we can use the classical 2-appx for $k$-center to select a set $S$ of centers such that every vertex is within a distance of 2 of some center in $S$.

Note that this procedure often selects fewer than $k$ centers since it only needs to cover everything with a radius of 2, while OPT covers everything (with $k$ centers) with a radius of 1.

I am considering a stronger version of the $k$-center problem:

Is there a way to select $k$ centers in a graph such that there is an OPTIMAL set of centers $S^*$ with every node in $S^*$ adjacent to a node we select?

I suspect that an algorithm for this problem should use the Hochbaum-Shmoys procedure to select some $k'$ centers, then place the extra centers in some clever way to ensure the stronger condition.