2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

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.