An $(\alpha,\beta)$-ruling set is a set $S$ such that any two nodes in $S$ are at distance at least $\alpha$ from each other, and, for any node $v \notin S$, there exists a node $u \in S$ such that the distance between $u$ and $v$ is at most $\beta$.

Let $G$ be graph which is nearly regular, with all degrees in $[k,2k]$.

Consider the following creation of the set $S$:

each vertex $v$ chooses a random number $r_v$ uniformly in $[0,1]$. If $r_v$ is local minima, namely $r_v < r_u$ for any neighbor $u \in N(v)$, then $v$ joins the set $S$.

I want to show that with high-probability, it has a set $S$ which is a $(2,O(\log n))$ ruling set.

Proving the $\alpha$ part is easy, because from the creation of $S$, only one vertex in $N^{+}(v)$ can be a local minima, and will be in $S$.

Proving the $\beta$ part is more difficult.

I can prove that $Pr[S \cap N^{+}(v) \ne \emptyset]$ for every $v$ with high probability. But not sure how to continue from here.

Help would be appreciated


1 Answer 1


I was about to complain that this statement:

Then, I can prove that $Pr[S \cap N^{+}(v) \ne \emptyset]$ for every $v$ with high probability

is probably wrong, because it would imply a stronger result, namely that nearly regular graphs have a $(2, 1)$ ruling set w.h.p.

But then I realised that, not only does this stronger claim actually hold, an even stronger claim holds, and is almost trivial to show:

Theorem: Every graph has a $(2, 1)$ ruling set.

Proof sketch: Choose any vertex $v$, add it to $S$, and remove it and its neighbours (which have distance 1 from $v$). Repeat until no vertices remain. Every pair of vertices in $S$ have distance $\ge 2$ since the only vertices with distance 1 are neighbours, and we removed all of those.

This claim is stronger than the original in three ways: It applies to every graph (not just nearly regular graphs), always (not just w.h.p.), and $1 < \log n$ except on a finite number of graphs.

This makes me wonder if you missed a condition.

  • $\begingroup$ First of all, thanks for the answer. Moreover, you were right, I missed a condition, the question asks about a specific set $S$ to be a ruling set. $\endgroup$
    – Gabi G
    Commented Jul 13, 2023 at 18:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.