Question

Prove that the following problem is in NP: Given a digraph G over n vertices (n is an even number), does G contain 2 vertex-disjoint simple cycles in which each cycle is of length n/2?

Answer 1

A problem P is in NP if and only if it is a decision problem with output Yes or No. And for every Yes output, its solution is verifable in polynomial time.

Since this problem is a decision problem and below is the verifier with solution consisting of set C1 and C2 i.e. vertex disjoint cycle C1 and C2 and each should be of length n/2.

Verifier(G=(V,E), C1, C2)

1. If |V| mod 2 = 1 then return False //since number of vertices are odd and hence such cycle cannot exist

2. If |C1| |V|/2 or |C2| |V|/2 then return False //if number of vertices in each cycle is not n/2 then return false

3. If then return False //since cycle must be disjoint

4. For every edge (u,v) in C1:-

5.........If then return False //since every edges in cycle must be part of edge set E

6. For every edge (u,v) in C2:-

7.........if then return False

8. If C1 and C2 contains |V|/2 vertices and edges in sequence forming a cycle then return True

9. else return False

Since each step of the verifier is done in polynomial time of the input size, hence the verifier is polynomial time verifier and the given problem is in NP.

Please comment for any clarification.