1
$\begingroup$

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?

$\endgroup$

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.