3
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ I think the difference is that these are induced cycles, and in the other question, there was no mention of induced. $\endgroup$
    – nvcleemp
    Feb 1, 2014 at 7:49
  • $\begingroup$ @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. $\endgroup$ Feb 1, 2014 at 8:55
  • $\begingroup$ @MohammadAl-Turkistany OK, I see, I will delete the comment. $\endgroup$
    – joro
    Feb 1, 2014 at 9:08
  • $\begingroup$ @joro Thanks for your valuable comments. I edited the post to clarify it. $\endgroup$ Feb 1, 2014 at 9:32
  • $\begingroup$ Won't you get a hamiltonian path if you can do this? $\endgroup$
    – joro
    Feb 1, 2014 at 14:12

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.