1
$\begingroup$

Define

$A = \{<G,s,t> :G$ is un directed graph that has a Hamilton path from $s$ to $t\}$

$B = \{<G> :G$ is un directed graph that has a Hamilton path$\}$

I would like to show that $A \le_p B$.

My attempt:

Given $<G,s,t>$ , the reduction outputs $<G'>$ where $G'$ defines as follows:

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$.

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\} \}$.

Now, if $<G,s,t> \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'$.

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.

$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jun 15 '17 at 12:48
  • 2
    $\begingroup$ What is your question? $\endgroup$ – Raphael Jun 15 '17 at 12:48
  • $\begingroup$ @Raphael if this reduction works, im stuck on proving the other direction, if it doesn't i would like to know what would work. $\endgroup$ – infinity Jun 15 '17 at 12:59
  • 1
    $\begingroup$ We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. The purpose of this kind of exercise is for you to get practice with reductions; we don't need the practice, and if we solved it for you, you wouldn't get the benefit of practice. We've written lots about reductions on this site -- see reductions, or look at some examples in a textbook on the subject. $\endgroup$ – D.W. Jun 15 '17 at 16:52
  • $\begingroup$ @D.W. sorry but i dont get you. i did not look for an easy way. i tried to solve it alone, and got stuck in the middle , and asked for some guidance. i am familiar with some reductions, this one just dont work for me. $\endgroup$ – infinity Jun 15 '17 at 16:56
1
$\begingroup$

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$.

$\endgroup$

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.