<p>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$.</p>

<p>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.</p>

<p>I am considering a stronger version of the $k$-center problem:</p>

<p>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?</p>

<p>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.</p>

CC BY-SA 4.0
2020-06-24T17:07:49.970Z
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
CC BY-SA 4.0
2020-06-29T19:09:48.080Z
We are given a graph with a dominating set of size $k$. That is what I'm calling OPT.
Karagounis Z
CC BY-SA 4.0
2020-06-30T01:56:12.073Z
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
CC BY-SA 4.0
2020-07-01T05:29:35.427Z
here just look at this question, its stated much more clearly
https://cstheory.stackexchange.com/questions/41415/finding-a-set-which-dominates-the-minimum-dominating-set
Karagounis Z
<graph-theory><graph-algorithms><approximation-algorithms><clustering>
k-center 2.0: A stronger k-center condition
Karagounis Z
# k-center 2.0: A stronger k-center condition

(Asked by: username_0 on 2018-06-15)

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.

**Tags:** graph-theory, graph-algorithms, approximation-algorithms, clustering
> **Comments:**
> **username_1**: 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.  
> **username_0**: We are given a graph with a dominating set of size $k$. That is what I'm calling OPT.  
> **username_1**: 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?  
> **username_0**: here just look at this question, its stated much more clearly https://cstheory.stackexchange.com/questions/41415/finding-a-set-which-dominates-the-minimum-dominating-set  

---

## 0 answers

