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$
6
  • $\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
    Commented Jun 15, 2017 at 12:48
  • 2
    $\begingroup$ What is your question? $\endgroup$
    – Raphael
    Commented Jun 15, 2017 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
    Commented Jun 15, 2017 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.
    Commented Jun 15, 2017 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
    Commented Jun 15, 2017 at 16:56

1 Answer 1

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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.