The Hamiltonian Path problem is a variation of the Hamiltonian Cycle problem but asked only whether there is a Hamiltonian path through all verticies, but does not require the path to return to the starting vertex.

Why is the Hamiltonian path problem solvable in polynomial time?

Select one:

a) Because the Hamiltonian Path problem can be solved by a Linear Bounded Automaton.

b) Because the reduction from SAT to the Hamiltonian Cycle problem required the path to return to the starting vertex.

c) Trick question! We can also reduce SAT to the Hamiltonian Path problem by adapting the reduction for the Hamiltonian Cycle problem.

d) Because it is easier to find a path than it is to find a cycle.

e) Because it is possible to check whether a graph has a Hamiltonian Path by checking that the degree of all its verticies is even, except for the start and end vertex whose degree can be odd.