# 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.

• I did not understand the first statement. How is the optimal always 1? Consider a path of length 3 and $k$ = 1. The optimal here is 2. – Inuyasha yagami Jun 24 at 17:07
• We are given a graph with a dominating set of size $k$. That is what I'm calling OPT. – Karagounis Z Jun 29 at 19:09
• Thanks for the clarification. I want to clarify another thing. Are you looking for a center set $S^{*}$ such that the subgraph on $S^{*}$ is connected and $S^{*}$ is a dominating set? – Inuyasha yagami Jun 30 at 1:56
• here just look at this question, its stated much more clearly cstheory.stackexchange.com/questions/41415/… – Karagounis Z Jul 1 at 5:29