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.

  • $\begingroup$ 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. $\endgroup$ Jun 24, 2020 at 17:07
  • $\begingroup$ We are given a graph with a dominating set of size $k$. That is what I'm calling OPT. $\endgroup$ Jun 29, 2020 at 19:09
  • $\begingroup$ 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? $\endgroup$ Jun 30, 2020 at 1:56
  • $\begingroup$ here just look at this question, its stated much more clearly cstheory.stackexchange.com/questions/41415/… $\endgroup$ Jul 1, 2020 at 5:29


Your Answer

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