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.

  • $\begingroup$ I guess this can be expressed as an instance of 1-in-3 3-SAT with $2n$ variables and $2n$ 1-in-3 3-CNF clauses. There's a variable $x_v$ for each vertex $v$, which is true if $v$ is in the first $n$-cycle. Is there any reason to think that such instances of 1-in-3 3SAT are easy? None that I know of. $\endgroup$ – D.W. Oct 13 '14 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.