1. Other
2. Other
3. give a polynomialtime reduction from hamiltonian path to hamiltonian...

Question: give a polynomialtime reduction from hamiltonian path to hamiltonian...

Question details

Give a polynomial-time reduction from Hamiltonian Path () to Hamiltonian Cycle (). You should prove that:

1. If is in , then is in .

2. If is not in , then is not in .

3. can be computed in time polynomial in .