<p>Based on <a href="https://math.stackexchange.com/questions/64113/is-there-an-efficient-algorithm-to-determine-the-parity-of-the-longest-path-in-a/64115#64115">Gadi's answer on Math.SE</a> (which proves NP-hardness using a Cook reduction), here is a proof of NP-hardness using a Karp reduction (as requested).</p>
<h2>General case</h2>
<p>The reduction is from Hamiltonian Cycle through Hamiltonian Path.</p>
<h3>Part 1: Hamiltonian Cycle <span class="math-container">$\le_m^P$</span> Hamiltonian Path</h3>
<p>We begin with a graph <span class="math-container">$G$</span> with <span class="math-container">$n$</span> 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,</p>
<ul>
<li>pick a vertex <span class="math-container">$v \in G$</span>,</li>
<li>add a vertex <span class="math-container">$v_0$</span>,</li>
<li>for each edge <span class="math-container">$(v, u)$</span>, add an edge <span class="math-container">$(v_0, u)$</span>,</li>
<li>add vertices <span class="math-container">$u_1$</span> and <span class="math-container">$u_2$</span>, and</li>
<li>add edges <span class="math-container">$(v, u_1)$</span> and <span class="math-container">$(v_0, u_2)$</span>.</li>
</ul>
<p>Call this graph <span class="math-container">$G_1$</span>. If <span class="math-container">$G$</span> has a Hamiltonian cycle, then <span class="math-container">$G_1$</span> has a Hamiltonian path (that with end points <span class="math-container">$u_1$</span> and <span class="math-container">$u_2$</span>). If <span class="math-container">$G_1$</span> has a Hamiltonian path, then it's end points must be <span class="math-container">$u_1$</span> <span class="math-container">$u_2$</span> since they have degree one, so other vertices in the Hamiltonian path give a Hamiltonian cycle when equating <span class="math-container">$v$</span> and <span class="math-container">$v_0$</span>.</p>
<h3>Part 2: Hamiltonian Path <span class="math-container">$\le_m^P$</span> Parity of Longest Path Even</h3>
<p>This reduction continues the one started above, so we have the graph <span class="math-container">$G_1$</span> with <span class="math-container">$n_1 = n + 3$</span> vertices.</p>
<p>If <span class="math-container">$n_1$</span> is odd, then a Hamiltonian path in <span class="math-container">$G_1$</span> (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 <span class="math-container">$n_1 - 2$</span> to <span class="math-container">$G_1$</span> to form a graph <span class="math-container">$G_2$</span>.</p>
<p>If <span class="math-container">$n_1$</span> is even, then a Hamiltonian path in <span class="math-container">$G_1$</span> (if one exists) would have to be of odd length. The case of odd <span class="math-container">$n_1$</span> is better, so we reduce to it by adding a vertex <span class="math-container">$w$</span> and edge <span class="math-container">$(w, u_1)$</span>, forming a graph <span class="math-container">$G_2$</span>. Now, a Hamiltonian path in <span class="math-container">$G_1$</span> (if one exists) would have to be of even length (and have end points <span class="math-container">$w$</span> and <span class="math-container">$u_2$</span> since they both have degree one), so we complete the reduction as above by adding a disjoint path of length <span class="math-container">$n_1 - 1$</span> to form a graph <span class="math-container">$G_2$</span>.</p>
<p>If <span class="math-container">$G_1$</span> contains a Hamiltonian path, then the length of the longest path in <span class="math-container">$G_2$</span> is even (of length <span class="math-container">$n_1 - 1$</span> when <span class="math-container">$n_1$</span> is odd and of length <span class="math-container">$n_1$</span> when <span class="math-container">$n_1$</span> is even). If <span class="math-container">$G_2$</span> contains a longest path of even length, then <span class="math-container">$G_1$</span> 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.</p>
<h2>Restricted to cubic graphs</h2>
<p>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 <em>Yes iff the parity of the longest path is even</em> is contrary what I have always heard regarding parity, which is the algorithm says <em>Yes iff the parity is odd</em>.</p>
<h2>Restricted to cubic (and planar) graphs when Yes iff longest path of odd parity</h2>
<p>The reduction for the general case can be made to work for cubic planar graphs when the algorithm says <em>Yes iff the parity of the longest path is odd</em>.</p>
<p>This time, we reduce from Hamiltonian Path directly. Thus, we begin with a cubic planar graph <span class="math-container">$G$</span> with <span class="math-container">$n$</span> vertices and want to know if it contains a Hamiltonian path.</p>
<p>Since <span class="math-container">$n$</span> is even, we want to add a disjoint graph with a longest path of size <span class="math-container">$n-2$</span>. This is possible for <span class="math-container">$n \ge 10$</span> as pictured...
<img src="https://i.sstatic.net/NDVqP.png" alt="path gadget" />
...since that is the shortest (even) length of the longest path possible via this path gadget.</p>
<p>For <span class="math-container">$n &lt; 10$</span>, we do a brute force search for the existence of a Hamiltonian path in <span class="math-container">$G$</span> and add the smallest path gadget if we don't find one.</p>

CC BY-SA 3.0
2011-09-15T05:14:49.143Z
Thanks Tyson. I guess Karp reduction uses only one function such that a $a \in A$ iff $f(a) \in B$
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-09-15T06:08:14.137Z
You might want to edit the picture. The graph pictured isn't cubic. :)
Timothy Sun
CC BY-SA 3.0
2011-09-15T12:17:51.247Z
@Mohammad This is a single function...a single function with a couple if-statements so that it can behave differently (1) when $n < 10$, (2) when $n \ge 10$ and odd, and (3) when $n \ge 10$ and even. It has the two necessary properties of a Karp reduction, namely, (1) $a \in A \iff f(a) \in B$ and (2) runs in deterministic polynomial time.
Tyson Williams
CC BY-SA 3.0
2011-09-15T13:26:36.657Z
If n is even, and you add a vertex to G and connect it to all the vertices, wont you sometimes create Hamiltonian paths even if none existed before? e.g., G is a disjoint union of 2 paths.
Robin Kothari
CC BY-SA 3.0
2011-09-15T14:34:06.293Z
@Robin Ah, yes. I introduced this problem when trying to simplify the reduction by reducing from HamPath instead of starting with HamCycle, which was my original thought. Edited the answer to use this other reduction.
Tyson Williams
CC BY-SA 3.0
2011-09-15T01:34:10.863Z
2011-09-15T14:30:34.863Z
2020-06-17T09:38:08.363Z
Tyson Williams
<p>No, it is not possible to efficiently calculate the parity of the longest path of an arbitrary graph, because it is possible to design such a graph, where any calculation of the that parity implies the comparision of the lengths of longest paths of two or more sub-graphs.</p>

<p>Consider this:</p>

<hr>

<p>One node s connects three components of a graph, and the longest path goes through that node s, like this:</p>

<pre><code>A=s-t=B
  |
  C
</code></pre>

<p><code>C</code> can trivially be designed to contain the longest of all paths that start at s.
So, either the longest path of the whole graph is partially in A or in B.</p>

<p><code>A</code> and <code>B</code> can be created out of two arbitrary graphs with a longest path of unknown length like this:</p>

<p>Starting with an arbitrary graph,</p>

<pre><code>1-2-3
</code></pre>

<p>each edge will be expanded to length 2,
and each vertex will be connected to an additional "dangling" edge of length 2.</p>

<pre><code>|  |  |
|  |  |
1--2--3        =  A
</code></pre>

<p>The longest path in this resulting graph is always even and will map to the longest path of the original graph. To "catch" one end of that longest path (in the resulting graph), each vertex will be directly connected to an additional "starting vector" s (or t). All longest of those paths starting at that specific vector are now odd.</p>

<pre><code>|  |  |
|  |  |
1--2--3        = A=s
 \ | /
   s
</code></pre>

<p>Two such constructed graphs (<code>A=s</code> and <code>B=t</code>) can now be combined with an edge between their individual starting vertices (s and t). One of those vertices will be connected to <code>C</code>, so that the longest path of the resulting graph will have one end in <code>C</code> and the other end in either <code>A</code> or <code>B</code>.</p>

<pre><code>A=s-t=B
  |
  C
</code></pre>

<p>Knowing the parity of the longest path of this resulting graph implies knowing whether the path ends in <code>A</code> or <code>B</code>.</p>

<p>Iff the longest path of the resulting graph ends in <code>A</code>, then the longest path of the original graph of <code>A</code> has to be longer than the longest path of the original graph of <code>B</code>.</p>

<hr>

<p>Iff there would be an efficient algorithm to determine the parity of the longest path in a graph, then there would be an efficient algorithm to compare the lengths of the longest paths of two different graphs, and vice versa.</p>

<hr>

<p>Of course, there exists a simpler proof by reducing this parity problem to that of the existance of an Hamiltonian path, but that proof would have been too easy.</p>

CC BY-SA 3.0
2011-09-14T04:19:14.857Z
What's wrong with "too easy"?
Timothy Sun
CC BY-SA 3.0
2011-09-29T02:33:05.503Z
If the question is easy, then the answer has to be either hard and fascinating or surprising or …boring: Easy questions with no easy answers are fascinating, but they might be too hard (or even unsolved). Therefore it is fun to find elegant but non-trivial answers. Remember the questions "Why are there infinite prime numbers?" or "How to calculate Pi?"? Anyway, sometimes an easy answer depends on the understanding of different topics or references to unknown technical terms, so I did not want to reduce this proof to properties of the Hamiltonian path, which might cause follow-up questions.
comonad
CC BY-SA 3.0
2011-09-14T01:36:05.763Z
2011-09-14T01:46:07.733Z
2011-09-14T01:46:07.733Z
comonad
<p>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?</p>

<p>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?</p>

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

<p>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.</p>

<p>Cross posted on <a href="https://math.stackexchange.com/questions/64113/is-there-an-efficient-algorithm-to-determine-the-parity-of-the-longest-path-in-a">Math StackExchange</a> </p>

CC BY-SA 3.0
2011-09-13T15:53:58.157Z
just a friendly reminder about the [policy](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231) for cross-posting.
Kaveh
CC BY-SA 3.0
2011-09-13T16:42:35.593Z
Didn't you already get an answer @ Math.SE?
Jukka Suomela
CC BY-SA 3.0
2011-09-13T17:55:09.407Z
Can you explain why you believe it is not correct?
Andrew D. King
CC BY-SA 3.0
2011-09-14T03:40:11.863Z
How is that a counterexample?
Robin Kothari
CC BY-SA 3.0
2011-09-14T03:59:55.000Z
@Robin, It is not. I deleted it.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-09-14T04:59:09.970Z
@Andrew, I was expecting Karp reduction but it seems to be a correct Cook reduction of NP-hardness
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-09-14T12:16:54.317Z
I do not think that you have understood Gadi A’s answer on math.stackexchange.com.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-14T13:27:00.250Z
@Tsuyoshi, Do you imply that it is Karp reduction? I see it as Cook reduction.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-09-14T13:37:17.783Z
@Tsuyoshi, My problem is LPEP={graph G: the longest path in G has even lenght }
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-09-14T13:48:46.657Z
The answer proves intractability and I accepted it. I was waiting for Karp redution.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-09-14T14:22:44.187Z
Gadi A’s answer gives a Karp reduction, although details of the reduction may depend on the details of the problem that you did not include in the question (e.g. longest path in which sense).  Why don’t you ask that as a comment on math.stackexchange.com?
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-14T14:25:20.620Z
The answer in math.stackexchange constructs a graph for each pair of vertices.  How about taking the disjoint union of all of them?  I think it gives you a Karp reduction.
Yoshio Okamoto
CC BY-SA 3.0
2011-09-14T14:26:32.067Z
By the way, do not assume that people read comments.  There is no way to tell from your question that you think that Gadi A’s answer gives only a Cook reduction and that you want a Karp reduction, so the question looks just redundant to those who do not read comments.
Tsuyoshi Ito
<cc.complexity-theory><ds.algorithms><graph-theory>
Is there an efficient algorithm to determine the parity of the longest path in a graph?
Mohammad Al-Turkistany
# Is there an efficient algorithm to determine the parity of the longest path in a graph?

(Asked by: username_0 on 2011-09-13)

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](https://math.stackexchange.com/questions/64113/is-there-an-efficient-algorithm-to-determine-the-parity-of-the-longest-path-in-a)

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory
> **Comments:**
> **username_1**: just a friendly reminder about the [policy](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231) for cross-posting.  
> **username_2**: Didn't you already get an answer @ Math.SE?  
> **username_3**: Can you explain why you believe it is not correct?  
> **username_4**: How is that a counterexample?  
> **username_0**: @Robin, It is not. I deleted it.  
> **username_0**: @Andrew, I was expecting Karp reduction but it seems to be a correct Cook reduction of NP-hardness  
> **username_5**: I do not think that you have understood Gadi A’s answer on math.stackexchange.com.  
> **username_0**: @Tsuyoshi, Do you imply that it is Karp reduction? I see it as Cook reduction.  
> **username_0**: @Tsuyoshi, My problem is LPEP={graph G: the longest path in G has even lenght }  
> **username_0**: The answer proves intractability and I accepted it. I was waiting for Karp redution.  
> **username_5**: Gadi A’s answer gives a Karp reduction, although details of the reduction may depend on the details of the problem that you did not include in the question (e.g. longest path in which sense).  Why don’t you ask that as a comment on math.stackexchange.com?  
> **username_6**: The answer in math.stackexchange constructs a graph for each pair of vertices.  How about taking the disjoint union of all of them?  I think it gives you a Karp reduction.  
> **username_5**: By the way, do not assume that people read comments.  There is no way to tell from your question that you think that Gadi A’s answer gives only a Cook reduction and that you want a Karp reduction, so the question looks just redundant to those who do not read comments.  

---

## 2 answers

### Answer by username_7 on 2011-09-15. Score: 4

Based on [Gadi's answer on Math.SE](https://math.stackexchange.com/questions/64113/is-there-an-efficient-algorithm-to-determine-the-parity-of-the-longest-path-in-a/64115#64115) (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...
![path gadget](https://i.sstatic.net/NDVqP.png)
...since that is the shortest (even) length of the longest path possible via this path gadget.

For $n < 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.

> **Comments:**
> **username_0**: Thanks Tyson. I guess Karp reduction uses only one function such that a $a \in A$ iff $f(a) \in B$  
> **username_8**: You might want to edit the picture. The graph pictured isn't cubic. :)  
> **username_7**: @Mohammad This is a single function...a single function with a couple if-statements so that it can behave differently (1) when $n < 10$, (2) when $n \ge 10$ and odd, and (3) when $n \ge 10$ and even. It has the two necessary properties of a Karp reduction, namely, (1) $a \in A \iff f(a) \in B$ and (2) runs in deterministic polynomial time.  
> **username_4**: If n is even, and you add a vertex to G and connect it to all the vertices, wont you sometimes create Hamiltonian paths even if none existed before? e.g., G is a disjoint union of 2 paths.  
> **username_7**: @Robin Ah, yes. I introduced this problem when trying to simplify the reduction by reducing from HamPath instead of starting with HamCycle, which was my original thought. Edited the answer to use this other reduction.  

---

### Answer by username_9 on 2011-09-14. Score: 1

No, it is not possible to efficiently calculate the parity of the longest path of an arbitrary graph, because it is possible to design such a graph, where any calculation of the that parity implies the comparision of the lengths of longest paths of two or more sub-graphs.
Consider this:

One node s connects three components of a graph, and the longest path goes through that node s, like this:
A=s-t=B
  |
  C

C can trivially be designed to contain the longest of all paths that start at s.
So, either the longest path of the whole graph is partially in A or in B.
A and B can be created out of two arbitrary graphs with a longest path of unknown length like this:
Starting with an arbitrary graph,
1-2-3

each edge will be expanded to length 2,
and each vertex will be connected to an additional "dangling" edge of length 2.
|  |  |
|  |  |
1--2--3        =  A

The longest path in this resulting graph is always even and will map to the longest path of the original graph. To "catch" one end of that longest path (in the resulting graph), each vertex will be directly connected to an additional "starting vector" s (or t). All longest of those paths starting at that specific vector are now odd.
|  |  |
|  |  |
1--2--3        = A=s
 \ | /
   s

Two such constructed graphs (A=s and B=t) can now be combined with an edge between their individual starting vertices (s and t). One of those vertices will be connected to C, so that the longest path of the resulting graph will have one end in C and the other end in either A or B.
A=s-t=B
  |
  C

Knowing the parity of the longest path of this resulting graph implies knowing whether the path ends in A or B.
Iff the longest path of the resulting graph ends in A, then the longest path of the original graph of A has to be longer than the longest path of the original graph of B.

Iff there would be an efficient algorithm to determine the parity of the longest path in a graph, then there would be an efficient algorithm to compare the lengths of the longest paths of two different graphs, and vice versa.

Of course, there exists a simpler proof by reducing this parity problem to that of the existance of an Hamiltonian path, but that proof would have been too easy.

> **Comments:**
> **username_8**: What's wrong with "too easy"?  
> **username_9**: If the question is easy, then the answer has to be either hard and fascinating or surprising or …boring: Easy questions with no easy answers are fascinating, but they might be too hard (or even unsolved). Therefore it is fun to find elegant but non-trivial answers. Remember the questions "Why are there infinite prime numbers?" or "How to calculate Pi?"? Anyway, sometimes an easy answer depends on the understanding of different topics or references to unknown technical terms, so I did not want to reduce this proof to properties of the Hamiltonian path, which might cause follow-up questions.  

---

