Karp hardness of an equidistant vertex set

Question

What is the hardness of the following problem?

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

Output: YES if $G$ has an equidistant vertex set of size $k$, otherwise NO

$\DeclareMathOperator{\dist}{dist}$An equidistant vertex set is a set of vertices $V'\subseteq V$ such that for every two pairs of vertices $u, v\in V'$ and $w, s\in V'$, we have $\dist(u, v) = \dist(w, s)$, where $\dist(u, v)$ is the length of a shortest path between $u$, $v$.

Answer 1

Your problem is NP-hard, by reduction from E3SAT, an NP-hard variant of 3SAT in which every clause involves 3 different variables.

Let $C_1 \lor \cdots \lor C_m$ be an instance of 3SAT; we can assume that $m$ is larger than some constant, since otherwise we can brute force the answer in constant time. We construct the following graph:

• Vertices: There is a vertex $(C_i,\ell)$ for each clause $C_i$ and for each literal $\ell$ appearing in the clause.
• Edges: We connect $(C_i,\ell)$ and $(C_j,\ell')$ if $i \neq j$ and $\ell \neq \lnot \ell'$.

Here are a few claims:

1. The formula is satisfiable iff the graph contains an $m$-clique. Indeed, if the formula is satisfiable, we choose one satisfied literal from each clause, and these are the vertices of the clique. In the other direction, an $m$-clique must identify a literal from each clause. These literals are non-contradictory, and so correspond to a (possibly partial) satisfying truth assignment.

2. The diameter of the graph is 2. Indeed, given two vertices $(C_i,\ell),(C_j,\ell')$ (where possibly $i=j$), assuming $m \geq 3$ we can find a vertex $(C_k,\ell'')$ such that $k \neq i,j$ and $\ell''$ involves a different variable from $\ell,\ell'$.

3. If $(C_i,\ell)$ and $(C_j,\ell')$ are at distance exactly 2 then either $i = j$ or $\ell = \lnot \ell'$.

4. Suppose that $K$ is a "2-clique", that is, a set of vertices in which any two vertices are at distance exactly 2. Pick some $(C_i,\ell) \in K$. If all vertices in $K$ are of the form $(C_i,\cdot)$ then $|K| \leq 3$. Otherwise, let $(C_j, \lnot \ell) \in K$, where $j \neq i$. Every other vertex $(C_k, \ell') \in K$ must satisfy $k \neq i$ or $k \neq j$; suppose, without loss of generality, that $k \neq i$. Then $\ell' = \lnot \ell$. Since $(C_k, \lnot \ell)$ and $(C_j, \lnot \ell)$ are at distance 2, necessarily $j = k$. That is, in this case $|K| \leq 2$.

5. Therefore if $m \geq 4$, there is an equidistant vertex set of size $m$ iff the formula is satisfiable.