# Proof of NP-completeness of a special case of longest-path problem

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

• Hint: what if the graph is not connected? Jan 11 '15 at 23:32
• 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. Jan 11 '15 at 23:40
• You can easily prove that it is NP-complete using a reduction from Hamiltonian $s-t$ path. Just add enough nodes and link ....
– Vor
Jan 12 '15 at 8:10
• @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. Jan 12 '15 at 9:59
• @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) Jan 12 '15 at 10:52

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