# Log reduce PATH to DISTANCE-PATH

An instance of PATH is given by where G is a directed graph, s and t are nodes in the graph, it's a true instance if G has a path from s to t.

DISTANCE-PATH is similar, but with an extra requirement d and on an undirected graph. A true instance of this would be where G is an undirected graph and there exists a path of length d from s to t, and there isn't a shorter path.

Given directed , construct an undirected G' such that G' has a path from s to t of shortest length d iff G has a path from s to t.

The idea is to construct G' by making n copies of G, and each edge in G' connects one copy to the next.

I don't understand how d comes into play and how to ensure there are no shorter paths, should d be the number of copies of G made? Should G' connect the copies of G by connecting one t node to the next s node? I'm not sure how to approach this problem

The idea is to build a layer graph $G'=\left (V_1,...,V_n\right)$ with $n$ layers, where each layer is a copy of $V$. For each $(u,v)\in E$ we add the edges $\left\{(u_i,v_{i+1}) | 1\le i \le n-1\right\}$, where $u_i$ is the copy of $u$ in $V_i$. In addition we add self edges $\left\{(u_i,u_{i+1}) | u\in V, 1\le i\le n-1\right\}$. You then want to know whether there exists a path $s_1\rightsquigarrow t_n$. Since $G'$ is a layer graph, any path from $s_1$ to $t_n$ is of length $n-1$ (so you dont need to worry about shorter paths anymore). You should now be able to complete the details yourself.