If $P=NP$, then $LCP \in P$

I want to prove that if we assume $$P=NP$$, then we can find the longest cycle (maximal number of vertices, no repeated edges, only repeated vertex is the starting one) in an undirected graph in polynomial time. I was thinking about reducing the problem to finding a Hamiltonian cycle in a directed graph but don't know how to. Another attempt is to do a DFS from every vertex while keeping track of the cycle lengths, and choosing the longest at the end. Is one of my approaches correct?

• This is the longest cycle problem, which is well-known to be in $NP$. Apr 15 at 19:56
• If it is well-known to be in $\mathsf{NP}$, what is the problem about saying it is in $\mathsf{P}$ under the condition $\mathsf{P} = \mathsf{NP}$? Apr 15 at 20:23
• I think we pretend not to be aware of it here. Maybe that's why reduction can help. Apr 15 at 20:29

Given $$k$$ and the graph, determining whether there exists such a cycle of length $$\ge k$$ is a problem in NP. (Why? Because there exists a witness for yes-instances that can be checked in polynomial time.)

If P=NP, it follows that such problem is in P too, i.e., there is a polynomial-time algorithm $$A$$ that, given $$k$$ and a graph, determines whether the graph has such a cycle of length $$\ge k$$.

Then you can use algorithm $$A$$ to find the length of the longest cycle, by running it for $$k=1$$, $$k=2$$, $$k=3$$, $$k=4$$, etc., and finding the largest $$k$$ for which it finds such a cycle. This whole process completes in polynomial time, since a polynomial times the number of vertices is also a polynomial.

This gives you the length of the cycle. If you also want to know an example of such a cycle, then you can extend the approach as follows:

Consider the following decision problem: Given $$k$$ and a graph $$G$$ and a path $$v_1 \to \cdots \to v_t$$, determine whether there exists a cycle of length $$\ge k$$ that starts with the path $$v_1 \to \cdots \to v_t$$. This is certainly in NP, as there is a witness that can be checked in polynomial time.

If P=NP, it follows that this decision problem can be solved in polynomial time. Let $$A$$ be a polynomial-time algorithm for this problem.

Then we can use $$A$$ to find the largest $$k$$ such that there is a cycle of length $$k$$, then fix $$k$$ and try all possibilities for the first edge $$v_1 \to v_2$$ to find one possibility for the first edge that can be extended to a cycle of length $$k$$, then fix $$v_1 \to v_2$$ and try all possibilities for $$v_3$$ to find a possibility for the first two edges that can be extended to a cycle of length $$k$$, and so on, until you have found an entire cycle of length $$k$$. This whole process takes polynomial time, since each invocation of $$A$$ finishes in polynomial time, and you only use $$A$$ polynomially times ($$k$$, which is at most the number of vertices, times the number of edges, both of which are polynomial).

• Actually, this does not find the actual cycle, only its length (though it is unclear what OP was asking for). Apr 15 at 22:09
• @Nathaniel, good point. See updated answer, which should address that point.
– D.W.
Apr 16 at 0:02