5
$\begingroup$

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

Improve this question
$\endgroup$
13
  • 5
    $\begingroup$ just a friendly reminder about the policy for cross-posting. $\endgroup$
    – Kaveh
    Sep 13, 2011 at 15:53
  • 8
    $\begingroup$ Didn't you already get an answer @ Math.SE? $\endgroup$
    – Jukka Suomela
    Sep 13, 2011 at 16:42
  • 9
    $\begingroup$ Can you explain why you believe it is not correct? $\endgroup$
    – Andrew D. King
    Sep 13, 2011 at 17:55
  • 2
    $\begingroup$ How is that a counterexample? $\endgroup$
    – Robin Kothari
    Sep 14, 2011 at 3:40
  • 4
    $\begingroup$ I do not think that you have understood Gadi A’s answer on math.stackexchange.com. $\endgroup$
    – Tsuyoshi Ito
    Sep 14, 2011 at 12:16

2 Answers 2

Reset to default
4
$\begingroup$

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... path gadget ...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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks Tyson. I guess Karp reduction uses only one function such that a $a \in A$ iff $f(a) \in B$ $\endgroup$
    – Mohammad Al-Turkistany
    Sep 15, 2011 at 5:14
  • 2
    $\begingroup$ You might want to edit the picture. The graph pictured isn't cubic. :) $\endgroup$
    – Timothy Sun
    Sep 15, 2011 at 6:08
  • $\begingroup$ @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. $\endgroup$
    – Tyson Williams
    Sep 15, 2011 at 12:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – Robin Kothari
    Sep 15, 2011 at 13:26
  • $\begingroup$ @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. $\endgroup$
    – Tyson Williams
    Sep 15, 2011 at 14:34
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ What's wrong with "too easy"? $\endgroup$
    – Timothy Sun
    Sep 14, 2011 at 4:19
  • $\begingroup$ 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. $\endgroup$
    – comonad
    Sep 29, 2011 at 2:33

Your Answer

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

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