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

Question

$ L = \{ <G,k> |\ 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 = {<G,k >,<C>} $

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 $ <G,k > \in L $ then S is a simple cycle and the verifier will accept. and if $ <G,k > \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: $ <G,k> \in L $ there exist a cycle size k , the machine will recognize it and return true.

$ <G,k> \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?

Answer 1

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.