Following the success of the previous question:

Karp hardness of an equidistant vertex set

I continue to propse yet another computational problem. This time, we modify the notion of an equidistant vertex set to obtain the notion of a simply equidistant vertex set. A vertex set $V'\subseteq V$ is called simply equidistant if there exists some $\alpha\in \mathbb{N}$ such that for every $u, v\in V'$, there exists a simple path of length $\alpha$ connecting $u$, $v$.

Our problem:

Input: an undirected graph $G(V,E)$ and a natural number $k$

Output: YES if there exists a simply equidistant of size $k$, otherwise NO

What is the hardness of this problem?


Your Answer

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

Browse other questions tagged or ask your own question.