What is the complexity of finding a third Hamilton Cycle in cubic graph?

Question

According to Smith Theorem: if a cubic graph has a hamilton circuit then it must have a second one. SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit. It is known that SMITH is in PPA, but it is unknown whether is it PPA-complete.

More details of this problem can be found here: https://kintali.wordpress.com/tag/ppa-completeness/

According to Tutte[1]: Every edge of a cubic graph lies on an even number of Hamilton cycles.Consequently a cubic hamiltonian graph has at least three Hamilton cycles.

My question: Given one Hamilton Cycle, what is the complexity of finding a third Hamilton Cycle in cubic graph?

For the problem that given one Hamilton Cycle in a cubic graph, to find the second one, Thomason[2] gave an exponential time algorithm, which can be converted into a PPA-membership proof of SMITH. How about if given one Hamilton Cycle in a cubic graph, to find the THIRD one? If we still use the algorithm of Thomason, it is no better than exponential time, and it is at least in PPA. But can we do better?

[1] W.T. Tutte, On Hamiltonian circuits, J. London Math. Soc., 21 (1946), 98–101.

[2] A. G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs, Ann. Discrete. Math. 3 (1978), 259-268.

Answer 1

Thomason's algorithm surely is superpolynomial, and shows that the problem is in PPA. In [3] I described another algorithm, also exponential and shows PPA, which is just as simple and has the added feature that it is easier to show that it is superpolynomial. Towards your question, given the way in which each of those algorithms behaves, I would very much suspect that finding a third Hamilton cycle given the first one is no easier than to find the second one. But I am not sure whether that helps to solve the related question: if you are given two distinct Hamilton cycles already, can you find a third one? Which I suppose is what you had in mind here.

[3] T.R. Jensen, Simple algorithm for finding a second Hamilton cycle, Siberian Electronic Math. Reports 9 (2012) 151–155.