Semplice riduzione del ciclo hamiltoniano

Question

Hampath

• Ingresso: Un grafico non diretto $ G $ e 2 nodi $ s, t $

• Domanda: G contiene un percorso hamiltoniano da $ s $ a $ t $?

Hamcycle

• Ingresso: Un grafico non diretto $ G $ e un nodi $ s $

• Domanda: Fa $ G $ contenere un ciclo hamiltoniano a partire da $ s $?

Vorrei mostrare che Hamcycle è np-hard. Lo mostrerò facendo $ Hampath leq_p Hamcycle $ Poiché Hampath è noto per essere NP-completo.

---

Aggiungi bordo da t a s

Se c'è un Hampath, la riduzione mostra lì un Hamcycle

Se c'è un Hamcycle, allora c'è chiaramente un Hampath

---

Sopra è il mio intero tentativo. Mi chiedevo se potevo chiamare $ t $ Nella mia riduzione poiché non è usato come input in Hamcycle?