An independent set (IS) in a graph is a set $V' \subseteq V(G)$ of pairwise non-adjacent vertices.

I am interested in the generalization $c$-IS where two nodes in $V' \subseteq V(G)$ need to have distance at least $c$ to any other vertex in $V'$.

Has this problem been studied before?

  • 1
    $\begingroup$ Distance-$d$ Independent Set. $\endgroup$ – Pål GD Apr 8 '13 at 8:53

Yes, this is called ruling set. 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$. So a maximal independent set is a $(2,1)$-ruling set. (This is defined in [1] but there might be prior references.)

[1] Korman et al. Toward more localized local algorithms: removing assumptions concerning global knowledge. PODC '11 Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing Pages 49-58

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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