A cycle permutation graph is a cubic graph composed from two $n$-cycles each labeled $1, 2,..., n$, with additional edges connecting vertex $i$ in the first cycle to vertex $\pi(i)$ in the second, where $\pi$ is a permutation in $S_n$.
I am interested in the complexity of recognizing cycle permutation graphs. I guess it is NP-complete. I did not find any literature on the computational aspects of this class of cubic graphs.
Is the recognition problem of cycle permutation graphs $NP$-complete?
The input is a cubic graph. The problem is to determine whether it is a cycle permutation graph or not.