# Is there an efficient algorithm to determine the parity of the longest path in a graph?

Finding the longest path in a graph is intractable problem. Th decision version is $NP$-complete. However, Given a graph, Is there an efficient algorithm to determine the parity of the longest path in a graph?

The algorithm should output YES if the length of the longest path is even otherwise the output is NO. Also, What is the complexity if we restrict the input to cubic graphs?

-
cross posted on TCS stack exchange. cstheory.stackexchange.com/questions/8216/… – Mohammad Al-Turkistany Sep 13 '11 at 16:44