# Is $L = \{ \langle G,k\rangle \mid G$ has a simple cycle at length $k \}$ in P or in NP

$$L = \{ |\ G \ has \ a \ simple \ cycle \ at \ length \ k \}$$

I think this language is in NP but my friend thinks this language is in P.

NP proof: if a graph has a simple cycle of a specific length can be verified quickly if we are given the cycle as a certificate.We can check in polynomial time that the given cycle is simple (doesn't repeat vertices except the first and last to make a cycle) and that it has exactly k + 1 edges.

$$R_L = {,}$$

where C is a cycle of k size in the graph,{qstart,q2....qend} V verifier will:

1. take qstart, and follow the next q until reaching qend, if qend and qstart are different then reject. if the cycle has different number of nodes then k, regect. if that is not a simple cycle ( going over the same node twice), then regect
2. accept

so $$ \in L$$ then S is a simple cycle and the verifier will accept. and if $$ \notin L$$ then S is not a simple cycle, or the size is not k then will reject.

my friend proof in P: there exists a polynomial deterministic in the size of the input: for each <G,k>:

1. run a DFS for each vertex: a. check for a cycle of size k if not exactly k then reject (when running DFS reaching to the same vertex) if there is a simple cycle of size k then accept. b. if all reject then reject.

time complexity $$O((V+E) \cdot V)$$ the turning machine is deterministic. and: $$ \in L$$ there exist a cycle size k , the machine will recognize it and return true.

$$ \notin L$$ the machine will not find a cycle of size k and will reject

does my friend approach is correct and the language is in P?

• @Nathaniel what do u think? Mar 2 at 16:17
• I edited your title for readability purposes only. Mar 2 at 16:23
• @Nathaniel but do you have any knowledge about who is wrong and who is correct? Mar 2 at 16:26

## 1 Answer

Your understanding of how to demonstrate that a language belongs to NP is correct. If a language L consists of instances where each instance is a graph G and an integer k, and L is defined as the set of all instances <G,k> where G contains a simple cycle of length k, then yes, the verification process you've described can indeed be performed in polynomial time given a certificate (in this case, the cycle itself). This establishes that L is in NP.

Regarding your friend's argument for L being in P, the critical point is whether there exists an efficient polynomial-time algorithm to find a simple cycle of length k in a graph. The approach suggested by your friend involves running Depth-First Search (DFS) from each vertex to look for a cycle of exactly length k. However, there are some nuances that need to be addressed to evaluate the correctness and efficiency of this approach.

### Correctness

The idea of using DFS to find cycles is a standard approach in graph algorithms. DFS can indeed be used to find cycles in a graph, but finding a cycle of a specific length efficiently is more challenging. The complexity of finding a cycle of exactly length k using DFS from each vertex isn't as straightforward as O((V+E)⋅V) without more specifics on how these cycles of exactly length k are being identified during the DFS process.

### Efficiency

The claim of O((V+E)⋅V) time complexity for finding a cycle of exactly length k seems overly optimistic without further explanation. The process of checking every possible path of length k from each vertex doesn't straightforwardly translate to a polynomial-time operation for arbitrary k. As k grows, the number of potential paths to explore grows exponentially.

For small fixed values of k, it's possible to argue a polynomial-time complexity, but for arbitrary k, the problem of finding a simple cycle of exactly length k is more aligned with known hard problems. Specifically, the problem of finding a simple cycle of length k is NP-complete for general graphs, as it can be reduced from the Hamiltonian cycle problem, which is well-known to be NP-complete.

### Conclusion

The approach your friend suggested would need more detail to be evaluated as a correct polynomial-time algorithm for the problem. While DFS is a powerful tool in graph theory, using it to find cycles of a specific length efficiently for arbitrary k is not trivially in P as suggested. The primary challenge is that, without additional constraints or techniques, the search space for cycles of length k can become prohibitively large, leading to exponential time complexity in the worst case.

In summary, your assertion that the problem is in NP is correct, as verifying a solution is polynomially bounded.

• so this is in P right? Mar 2 at 16:23