Karp hardness of an equidistant vertex set

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$$.

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.

• Move on to view my question on the directed version cs.stackexchange.com/questions/97757/… Sep 25 '18 at 10:28
• We have managed to reduce from this (undirected) version to the digraph version in a neat hardness proof. Oct 10 '18 at 1:32