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.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Does it have to be exactly length $d$? Or is $\geq d$ okay? $\endgroup$– Luke MathiesonCommented Dec 3, 2012 at 2:12
-
$\begingroup$ it has to be exactly d. in other words, the shortest path from s to t has length d. $\endgroup$– Aden DongCommented Dec 3, 2012 at 3:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
answered Dec 3, 2012 at 8:27
-
$\begingroup$ 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. $\endgroup$ Commented Dec 3, 2012 at 9:06
-
$\begingroup$ Right, this is the same thing. $\endgroup$ Commented Dec 3, 2012 at 20:51