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$
7
  • $\begingroup$ Hint: what if the graph is not connected? $\endgroup$ Jan 11, 2015 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$ Jan 11, 2015 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, 2015 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$ Jan 12, 2015 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$ Jan 12, 2015 at 10:52

1 Answer 1

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