Reducing one variant of Hamiltonian path to another - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:07:34Z https://cs.stackexchange.com/feeds/question/76828 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/76828 1 Reducing one variant of Hamiltonian path to another user123 https://cs.stackexchange.com/users/67279 2017-06-15T12:00:04Z 2017-06-15T19:52:38Z <p>Define</p> <p>$A = \{&lt;G,s,t&gt; :G$ is un directed graph that has a Hamilton path from $s$ to $t\}$ </p> <p>$B = \{&lt;G&gt; :G$ is un directed graph that has a Hamilton path$\}$</p> <p>I would like to show that $A \le_p B$. </p> <p>My attempt: </p> <p>Given $&lt;G,s,t&gt;$ , the reduction outputs $&lt;G'&gt;$ where $G'$ defines as follows: </p> <p>we take $v_s$ and $v_t$ s.t there is an edge $e_s$ between $s$ and$v_s$ and an edge $e_t$ between $v_t$ and $t$.</p> <p>Now we define $G' = (V',E')$ where $V' = V \cup \{v_0 , v_1\}$ and $E' = (E-\{e' :e' \ne e_s , s\in e'\} -\{e' :e' \ne e_t , t\in e'\}) \cup \{ \{v_0,v \} :\{v,s\} \in E \} \cup \{ \{v_1,v \} :\{v,t\} \in E \} \cup \{ \{v_0,s \}\ , \{v_1,t\} \}$.</p> <p>Now, if $&lt;G,s,t&gt; \in A$ , let $s , u_1,\dots ,u_n ,t$ be the Hamilton path , then $s , v_0 , u_1 , \dots , u_n, v_1 ,t$ is a Hamilton path in $G'$. </p> <p>The other direction does not work for me , if $G'$ has a Hamilton path then I want to say that the "end points" must be around $s,t$ but i'm not sure how to do that.</p> https://cs.stackexchange.com/questions/76828/-/76848#76848 1 Answer by Yuval Filmus for Reducing one variant of Hamiltonian path to another Yuval Filmus https://cs.stackexchange.com/users/683 2017-06-15T19:51:59Z 2017-06-15T19:51:59Z <p>The simplest reduction, which is similar to what you were trying but simpler, is to add two new vertices to the graph in the instance of A: a vertex $v_s$ connected to $s$, and a vertex $v_t$ connected to $t$. Any Hamiltonian path in the new graph will connect $v_s$ to $v_t$, and so will restrict to a Hamiltonian path connecting $s$ to $t$. Vice versa, any Hamiltonian path in the original graph connecting $s$ to $t$ extends to a Hamiltonian path in the new graph connecting $v_s$ to $v_t$.</p>