0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ This is the longest cycle problem, which is well-known to be in $NP$. $\endgroup$ Apr 15 at 19:56
  • 2
    $\begingroup$ 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}$? $\endgroup$
    – Nathaniel
    Apr 15 at 20:23
  • $\begingroup$ I think we pretend not to be aware of it here. Maybe that's why reduction can help. $\endgroup$ Apr 15 at 20:29

1 Answer 1

2
$\begingroup$

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).

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.