2
$\begingroup$

Problem: Longest Path

Input: An undirected graph $G=(V,E)$

Question: Is there a path of length at least $\frac{|V|}4$?

I know that in order to prove the simple version of $k$ longest path, we reduce the Hamiltonian path to longest path. How we can prove the $NP$-completeness in this special case? Should I use a reduction from Hamiltonian cycle?

Edit: A hint : Reduction from Hamiltonian path. Try to think how many vertices should be added to a special instance $G'$ of Longest path problem so that if there is a path least $\frac{|V|}{4}$ vertices in length then there is a Hamiltonian path in $G$.

$\endgroup$
  • $\begingroup$ Hint: what if the graph is not connected? $\endgroup$ – Tom van der Zanden Jan 11 '15 at 23:32
  • $\begingroup$ sorry ,i should have mentioned that $G$ is connected. The only hint i know is that i should consider a new graph which contains extra nodes. $\endgroup$ – hardstudent Jan 11 '15 at 23:40
  • 3
    $\begingroup$ You can easily prove that it is NP-complete using a reduction from Hamiltonian $s-t$ path. Just add enough nodes and link .... $\endgroup$ – Vor Jan 12 '15 at 8:10
  • $\begingroup$ @Vor You can even more easily prove that it is NP-complete using a reduction from the usual "Is there a path of length at least $k$" version of longest path. $\endgroup$ – David Richerby Jan 12 '15 at 9:59
  • $\begingroup$ @Vor Can you be more specific please? i haven't solve something similar so i don't know how should i approach the problem.(or suggest a book/source so i can read about similar reductions) $\endgroup$ – hardstudent Jan 12 '15 at 10:52
1
$\begingroup$

We can prove that requiring the graph $G$ to be connected does not decrease the hardness of our problem here.

Reduce from Hamiltonian path between $2$ specified vertices, namely $s,t\in V(G)$

Like before, we want to add new vertices to the graph while keeping it connected.

Now, do some arithmetics:

A Hamiltonian path between $s$ and $t$ is of length $n-1$, where $n=|V|$

If we attach some paths of length (at most) $k$ to $s$ and $t$, then we can increase the length of a path up to $n-1+2k$.

We should have $4(n-1+2k)=|\mathcal{V}|$ in the new graph $\mathcal{G(V,E)}$.

So $|\mathcal{V}|-|V|=3n-4+8k$. Take $k=\sqrt{n}$. Alternatively, attach $s$ and then $t$ and again $s$, etc. to a new short path of length (at most) $k$ (i.e. $k$ new vertices).

The point of setting $k=\sqrt{n}$ is to prevent one from concatenating $2$ short paths attached to the same vertex (either $s$ or $t$). So, one must take one path attached to each vertex among $s$ and $t$. And the middle part of the path is a Hamiltonian path between $s$ and $t$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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