# Prove the following problem is NL-complete

Suppose $$A = \left\{\langle G, d, s, t\rangle \;\Bigg|\; \begin{array}{l} \text{$$G$$ undirected}, \\ \text{$$s$$ and $$t$$ are nodes in $$G$$}, \\ \text{there is a path of length $$d$$ from $$s$$ to $$t$$ and no path of shorter length} \end{array}\right\}$$ I can easily see that this language is in NL, but I am having trouble proving that this is NL-complete.

-
Does it have to be exactly length $d$? Or is $\geq d$ okay? – Luke Mathieson Dec 3 '12 at 2:12
it has to be exactly d. in other words, the shortest path from s to t has length d. – Aden Dong Dec 3 '12 at 3:27

Let $G'$ be the graph with self-loops added to every vertex. Take $n$ copies $G'_1,G'_2,\ldots,G'_n$ (without the edges) and connect $x \in G'_i$ to $y \in G'_{i+1}$ if $(x,y) \in G'$. The shortest path between $s \in G'_1$ and $t \in G'_n$, if any exists, is now of length exactly $n-1$.
If I'm interpreting correctly, you can get rid of the self loops and explicitly say something like "connect $x\in G_{i}$ to $y \in G_{i+1}$ if $(x,y)\in E(G)$ or $x=y$ (in $G$)", then we still have a simple graph. – Luke Mathieson Dec 3 '12 at 9:06