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?