I am aware that deciding the existence of a partition of the vertices of a connected graph $G(V, E)$ into two induced cycles is $NP$-complete(Theorem 2). Induced cycle is a cycle without any chord (cordless cycle or a hole).
I am interested in the complexity of this problem when restricted to cubic graphs and we require that the two induced cycles must have the same order.
Does the problem remain $NP$-complete when we restrict the input to cubic graphs and require that the two induced cycles have the same number of vertices?
Motivation The class of connected cubic graphs that admit a partition of the vertex set into two equal-size induced cycles is exactly the class of cycle permutation graphs. So, I'm interested in proving the $NP$-completeness of the recognition problem of this subclass of cubic graphs.
A cycle permutation graph is composed from two $n$-cycles each labeled $1, 2,..., n$, with additional edges connecting $i$ in the first cycle to $\pi(i)$ in the second, where $\pi ∈ S_n$.
EDIT: Cycle permutation graphs are highly connected cubic graph. I guess they are at least V/2-edge connected (I have no proof). Here, I am interested in hardness of recognition of cycle permutation graphs. I guess it is NP-complete. The computational properties of this class of graphs are not studied. I did not find any literature on the subject. I guess those graphs would have good applications in computer networks and bus systems of large-scale multi-processor systems.
Is the recognition problem of cycle permutation graphs $NP$-complete? Is it polynomial-time decidable?