0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry to bother you for further clarification. From your description, the picture I'm getting is this lattice structure with "vertical" edges through every vertex in the original vertex set, and "diagonal" edges from one level to the net on corresponding vertices whenever there's an edge in the original edge set. This way, if the original graph G has a path, there will be a path in G' going down one level at a time until it gets to the last level which will end on tn. That part makes sense, but what are the vertical self edges for in this case? $\endgroup$ – STL93 Mar 30 '16 at 2:52
  • $\begingroup$ In this solution we only have edges crossing between layers (we have no edges inside each layer). To see why the self edges (which simply take you to the next level, but keep you at the same vertex) are needed, try writing the complete proof. $\endgroup$ – Ariel Mar 30 '16 at 6:22

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.