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. The 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?

EDIT 1: I moved some of my comments here as requested by a friend. 

My problem is LPEP={graph G: the longest path in G has even length }. The answer of Gadi A proves intractability and I accepted it. I was waiting for Karp reduction.

Cross posted on Math StackExchange
Based on Gadi's answer on Math.SE (which proves NP-hardness using a Cook reduction), here is a proof of NP-hardness using a Karp reduction (as requested).
General case
The reduction is from Hamiltonian Cycle through Hamiltonian Path.
Part 1: Hamiltonian Cycle $\le_m^P$ Hamiltonian Path
We begin with a graph $G$ with $n$ vertices and want to know if it contains a Hamiltonian cycle.  We use a standard reduction to Hamiltonian Path (see Theorem 8.19 of Algorithm Design, which gives the directed graph version). Specifically,

pick a vertex $v \in G$,
add a vertex $v_0$,
for each edge $(v, u)$, add an edge $(v_0, u)$,
add vertices $u_1$ and $u_2$, and
add edges $(v, u_1)$ and $(v_0, u_2)$.

Call this graph $G_1$. If $G$ has a Hamiltonian cycle, then $G_1$ has a Hamiltonian path (that with end points $u_1$ and $u_2$). If $G_1$ has a Hamiltonian path, then it's end points must be $u_1$ $u_2$ since they have degree one, so other vertices in the Hamiltonian path give a Hamiltonian cycle when equating $v$ and $v_0$.
Part 2: Hamiltonian Path $\le_m^P$ Parity of Longest Path Even
This reduction continues the one started above, so we have the graph $G_1$ with $n_1 = n + 3$ vertices.
If $n_1$ is odd, then a Hamiltonian path in $G_1$ (if one exists) would have to be of even length. In this case, we use the same reduction as Gadi, which adds a disjoint path of length $n_1 - 2$ to $G_1$ to form a graph $G_2$.
If $n_1$ is even, then a Hamiltonian path in $G_1$ (if one exists) would have to be of odd length. The case of odd $n_1$ is better, so we reduce to it by adding a vertex $w$ and edge $(w, u_1)$, forming a graph $G_2$. Now, a Hamiltonian path in $G_1$ (if one exists) would have to be of even length (and have end points $w$ and $u_2$ since they both have degree one), so we complete the reduction as above by adding a disjoint path of length $n_1 - 1$ to form a graph $G_2$.
If $G_1$ contains a Hamiltonian path, then the length of the longest path in $G_2$ is even (of length $n_1 - 1$ when $n_1$ is odd and of length $n_1$ when $n_1$ is even). If $G_2$ contains a longest path of even length, then $G_1$ must contain a Hamiltonian path since we know there is a path of odd length that is one shorter than the length required in a Hamiltonian path.
Restricted to cubic graphs
I do not see how the reduction for the general case can be made to work for cubic graphs since all cubic graphs have an even number of vertices. However, your requirement that the algorithm should say Yes iff the parity of the longest path is even is contrary what I have always heard regarding parity, which is the algorithm says Yes iff the parity is odd.
Restricted to cubic (and planar) graphs when Yes iff longest path of odd parity
The reduction for the general case can be made to work for cubic planar graphs when the algorithm says Yes iff the parity of the longest path is odd.
This time, we reduce from Hamiltonian Path directly. Thus, we begin with a cubic planar graph $G$ with $n$ vertices and want to know if it contains a Hamiltonian path.
Since $n$ is even, we want to add a disjoint graph with a longest path of size $n-2$. This is possible for $n \ge 10$ as pictured...

...since that is the shortest (even) length of the longest path possible via this path gadget.
For $n &lt; 10$, we do a brute force search for the existence of a Hamiltonian path in $G$ and add the smallest path gadget if we don't find one.