Return to Question

HAMPATH

• Input: An undirected graph $G$ and 2 nodes $s, t$

• Question: Does G contain a Hamiltonian path from $s$ to $t$?

• Input: A undirected graph $G$ and a nodes $s$

• Question: Does $G$ contain a Hamiltonian cycle starting at $s$?

I wish to show HAMCYCLE is NP-hard. I'll show this by doing $HAMPATH \leq_p HAMCYCLE$ since HAMPATH is known to be NP-complete.

Reduction is as follows: $(G, s, t) \to (G', s')$ where $s' = s$ and for $G'$ I will add one edge from $t$ to $s'$.

This is polynomial time because we are adding only an edge.

If $(G, s, t) \in HAMPATH$, then we know there is a Hamiltonian path from $s$ to $t$, our graph $G'$ will be $(s', \dots, t)$ but since we added a edge from $t$ to $s'$ then

$(s', \dots, t, s')$, a cycle, thus $(G',s') \in HAMCYCLE$.

Now doing the converse, if $(G', s') \in HAMCYCLE$ then there exist a Hamiltonian cycle from $(s', ..., s')$ that visits every node and comes back to $s'$ meaning there is a node $t$ right before $s$ to make this a Hamiltonian path, thus $(G, s, t) \in HAMPATH$.

Above is my entire attempt. I was wondering if I could call on $t$ in my reduction since its not used as a input in HAMCYCLE?

HAMPATH

• Input: An undirected graph $G$ and 2 nodes $s, t$

• Question: Does G contain a Hamiltonian path from $s$ to $t$?

• Input: A undirected graph $G$ and a nodes $s$

• Question: Does $G$ contain a Hamiltonian cycle starting at $s$?

I wish to show HAMCYCLE is NP-hard. I'll show this by doing $HAMPATH \leq_p HAMCYCLE$ since HAMPATH is known to be NP-complete.

add edge from t to s

if theres a hampath then the reduction shows there a hamcycle

if theres a hamcycle then clearly theres a hampath

Above is my entire attempt. I was wondering if I could call on $t$ in my reduction since its not used as a input in HAMCYCLE?

HAMPATH

• Input: An undirected graph $G$ and 2 nodes $s, t$

• Question: Does G contain a Hamiltonian path from $s$ to $t$?

• Input: A undirected graph $G$ and a nodes $s$

• Question: Does $G$ contain a Hamiltonian cycle starting at $s$?

I wish to show HAMCYCLE is NP-hard. I'll show this by doing $HAMPATH \leq_p HAMCYCLE$ since HAMPATH is known to be NP-complete.

Reduction is as follows: $(G, s, t) \to (G', s')$ where $s' = s$ and for $G'$ I will add one edge from $t$ to $s'$.

This is polynomial time because we are adding only an edge.

If $(G, s, t) \in HAMPATH$, then we know there is a Hamiltonian path from $s$ to $t$, our graph $G'$ will be $(s', \dots, t)$ but since we added a edge from $t$ to $s'$ then

$(s', \dots, t, s')$, a cycle, thus $(G',s') \in HAMCYCLE$.

Now doing the converse, if $(G', s') \in HAMCYCLE$ then there exist a Hamiltonian cycle from $(s', ..., s')$ that visits every node and comes back to $s'$ meaning there is a node $t$ right before $s$ to make this a Hamiltonian path, thus $(G, s, t) \in HAMPATH$.

Above is my entire attempt. I was wondering if I could call on $t$ in my reduction since its not used as a input in HAMCYCLE?

Thanks to dkaeae for pointing out why it's wrong.

NEW ATTEMPT

Here is my other reduction that I've just tried. $s' = s$, and I add a new node $t'$. I form an edge $(t', t)$ and another edge $(t', s')$.

This is in polynomial because only 2 edges and 1 node were added to $G$.

if $(G, s, t) \in HAMPATH$, then there will be a hamilton path from $(s, \dots, t)$ and given this reduction there will be a hamilton cycle from $(s', \dots, t, t', s')$ \in HAMCYCLE.

if $(G', s') \in HAMCYCLE$, then there we know there is a HAMCYCLE $(s', \dots, t', s')$. We know there is a node $t'$ such that it points to s' after visiting every node to form a cycle, hence $(s', \dots, t')$ is a hamilton path $(G, s, t) \in HAMPATH $

HAMPATH

• Input: An undirected graph $G$ and 2 nodes $s, t$

• Question: Does G contain a Hamiltonian path from $s$ to $t$?

• Input: A undirected graph $G$ and a nodes $s$

• Question: Does $G$ contain a Hamiltonian cycle starting at $s$?

I wish to show HAMCYCLE is NP-hard. I'll show this by doing $HAMPATH \leq_p HAMCYCLE$ since HAMPATH is known to be NP-complete.

Reduction is as follows: $(G, s, t) \to (G', s')$ where $s' = s$ and for $G'$ I will add one edge from $t$ to $s'$.

This is polynomial time because we are adding only an edge.

If $(G, s, t) \in HAMPATH$, then we know there is a Hamiltonian path from $s$ to $t$, our graph $G'$ will be $(s', \dots, t)$ but since we added a edge from $t$ to $s'$ then

$(s', \dots, t, s')$, a cycle, thus $(G',s') \in HAMCYCLE$.

Now doing the converse, if $(G', s') \in HAMCYCLE$ then there exist a Hamiltonian cycle from $(s', ..., s')$ that visits every node and comes back to $s'$ meaning there is a node $t$ right before $s$ to make this a Hamiltonian path, thus $(G, s, t) \in HAMPATH$.

Above is my entire attempt. I was wondering if I could call on $t$ in my reduction since its not used as a input in HAMCYCLE?

HAMPATH

• Input: An undirected graph $G$ and 2 nodes $s, t$

• Question: Does G contain a Hamiltonian path from $s$ to $t$?

• Input: A undirected graph $G$ and a nodes $s$

• Question: Does $G$ contain a Hamiltonian cycle starting at $s$?

I wish to show HAMCYCLE is NP-hard. I'll show this by doing $HAMPATH \leq_p HAMCYCLE$ since HAMPATH is known to be NP-complete.

Reduction is as follows: $(G, s, t) \to (G', s')$ where $s' = s$ and for $G'$ I will add one edge from $t$ to $s'$.

This is polynomial time because we are adding only an edge.

If $(G, s, t) \in HAMPATH$, then we know there is a Hamiltonian path from $s$ to $t$, our graph $G'$ will be $(s', \dots, t)$ but since we added a edge from $t$ to $s'$ then

$(s', \dots, t, s')$, a cycle, thus $(G',s') \in HAMCYCLE$.

Now doing the converse, if $(G', s') \in HAMCYCLE$ then there exist a Hamiltonian cycle from $(s', ..., s')$ that visits every node and comes back to $s'$ meaning there is a node $t$ right before $s$ to make this a Hamiltonian path, thus $(G, s, t) \in HAMPATH$.

Above is my entire attempt. I was wondering if I could call on $t$ in my reduction since its not used as a input in HAMCYCLE?

Thanks to dkaeae for pointing out why it's wrong.

NEW ATTEMPT

Here is my other reduction that I've just tried. $s' = s$, and I add a new node $t'$. I form an edge $(t', t)$ and another edge $(t', s')$. So if $(G, s, t) \in HAMPATH$, then there will be a hamilton path from $(s, \dots, t)$ and given this reduction there will be a hamilton cycle from $(s', \dots, t, t', s')$ \in HAMCYCLE.

if $(G', s') \in HAMCYCLE$, then there we know there is a HAMCYCLE $(s', \dots, t', s')$. We know there is a node $t'$ such that it points to s' after visiting every node to form a cycle, hence $(s', \dots, t')$ is a hamilton path $(G, s, t) \in HAMPATH $

Clearly polytime because we only added 1 node and 2 edges

HAMPATH

• Input: An undirected graph $G$ and 2 nodes $s, t$

• Question: Does G contain a Hamiltonian path from $s$ to $t$?

• Input: A undirected graph $G$ and a nodes $s$

• Question: Does $G$ contain a Hamiltonian cycle starting at $s$?

I wish to show HAMCYCLE is NP-hard. I'll show this by doing $HAMPATH \leq_p HAMCYCLE$ since HAMPATH is known to be NP-complete.

Reduction is as follows: $(G, s, t) \to (G', s')$ where $s' = s$ and for $G'$ I will add one edge from $t$ to $s'$.

This is polynomial time because we are adding only an edge.

If $(G, s, t) \in HAMPATH$, then we know there is a Hamiltonian path from $s$ to $t$, our graph $G'$ will be $(s', \dots, t)$ but since we added a edge from $t$ to $s'$ then

$(s', \dots, t, s')$, a cycle, thus $(G',s') \in HAMCYCLE$.

Now doing the converse, if $(G', s') \in HAMCYCLE$ then there exist a Hamiltonian cycle from $(s', ..., s')$ that visits every node and comes back to $s'$ meaning there is a node $t$ right before $s$ to make this a Hamiltonian path, thus $(G, s, t) \in HAMPATH$.

Above is my entire attempt. I was wondering if I could call on $t$ in my reduction since its not used as a input in HAMCYCLE?

Thanks to dkaeae for pointing out why it's wrong.

NEW ATTEMPT

Here is my other reduction that I've just tried. $s' = s$, and I add a new node $t'$. I form an edge $(t', t)$ and another edge $(t', s')$.

This is in polynomial because only 2 edges and 1 node were added to $G$.

if $(G, s, t) \in HAMPATH$, then there will be a hamilton path from $(s, \dots, t)$ and given this reduction there will be a hamilton cycle from $(s', \dots, t, t', s')$ \in HAMCYCLE.

if $(G', s') \in HAMCYCLE$, then there we know there is a HAMCYCLE $(s', \dots, t', s')$. We know there is a node $t'$ such that it points to s' after visiting every node to form a cycle, hence $(s', \dots, t')$ is a hamilton path $(G, s, t) \in HAMPATH $