Simple Hamiltonian cycle reduction
-
05-11-2019 - |
Frage
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?
Keine korrekte Lösung
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange