Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
I think the difference is that these are induced cycles, and in the other question, there was no mention of induced. –  nvcleemp Feb 1 at 7:49
    
@joro They are not exactly the same. Cycle permutation graphs are highly connected cubic graph. I guess they are at least $V/2$-edge connected. Here, I am interested in hardness of recognition of cycle permutation graphs. I guess it is NP-complete. –  Mohammad Al-Turkistany Feb 1 at 8:55
    
@MohammadAl-Turkistany OK, I see, I will delete the comment. –  joro Feb 1 at 9:08
    
@joro Thanks for your valuable comments. I edited the post to clarify it. –  Mohammad Al-Turkistany Feb 1 at 9:32
    
Won't you get a hamiltonian path if you can do this? –  joro Feb 1 at 14:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.