patternMinor
Prove the following problem is NL-complete
Viewed 0 times
problemthefollowingprovecomplete
Problem
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.
$$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.
Solution
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$.
Context
StackExchange Computer Science Q#7115, answer score: 3
Revisions (0)
No revisions yet.