HAMPATH

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

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

HAMCYCLE

  • 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?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top