0
$\begingroup$

I have this question: I have an undirected graph G(V, E) (where V = set of vertices, E = set of edges). Consider the maximum path between two vertices s and t:

LPATH = {⟨G,s,t,k⟩|There is in G a simple path as long as at least k from s to t}

A simple path is a path without any repeated vertice, i.e. every vertice can be visited just one time. The length of the path is given from the edges of which it is composed.

So how can I show that LPATH is an NP-Complete problem using the Hamilton path problem as an NP-Hard problem as reference?

$\endgroup$

1 Answer 1

1
$\begingroup$

Welcome to the site!

A Karp reduction from $\mathrm{Hamiltonian Cycle}$ could work as follows: Given a graph $G = (V, E)$, we construct $\mathrm{Long Path}$-instance $(G', v, v', |V|)$ where $G'$ is obtained by adding a copy $v'$ of some arbitrarily chosen vertex $v \in V$ (including its edges). Note that this instance can be constructed from $G$ in polynomial time.

To see that this is a correct reduction mapping, we see that a Hamiltonian cycle $C$ in $G$ induces a path between $v$ and $v'$ of length $|V|$ and vice versa.

Thus, we have a polynomial reduction $\mathrm{Hamiltonian Cycle} \leq_\mathsf{P} \mathrm{Long Path}$, thus showing that your problem is $\mathsf{NP}$-hard (because $\mathrm{Hamiltonian Cycle}$ is $\mathsf{NP}$-hard already).

To show that $\mathrm{Long Path}$ is in $\mathsf{NP}$ we note that a path in a graph can be efficiently encoded as a list of its edges and checking that a string actually encodes a path in the graph and then counting the number of edges to determine whether it is long enough can be done in polynomial time.

Hence we find that $\mathrm{Long Path}$ is $\mathsf{NP}$-complete.

$\endgroup$
9
  • $\begingroup$ Nope, sorry. What I understand until now is that I have to prove LPATH is in NP and is NP-HARD. Now for being in NP there must be a polynomial algorithm that verifies a certain path (Ok maybe I can find it). To prove that is NP-HARD I need to show that I can reduce LPATH to HAMILTON but I still cannot understand how to do it. $\endgroup$
    – nene4496
    Jun 6, 2020 at 18:17
  • $\begingroup$ Actually the other way around: you need to show that $\mathrm{Hamiltonian Cycle} \leq_\mathsf{P} \mathrm{Long Path}$ to establish $\mathsf{NP}$-hardness. $\endgroup$ Jun 6, 2020 at 18:33
  • $\begingroup$ I edited the answer to give a more or less complete solution. I assumed that you meant the Hamiltonian cycle problem which, as far as I know, is more well-known than the problem of finding a Hamiltonian path. If I was mistaken in doing so, note that a Hamiltonian path is just a simple path of length $|V| - 1$ which is the maximum length of a simple path in a graph $G = (V, E)$ anyways. $\endgroup$ Jun 6, 2020 at 18:47
  • $\begingroup$ Perfect, thank you very much! I will let you know any other doubt but you were very clear, thank you again! $\endgroup$
    – nene4496
    Jun 7, 2020 at 13:22
  • $\begingroup$ Sorry, I don't understand why v and w must be connected, what if they're not connected? I think the question asks about two random vertices, not necessarily connected. And what about the minimum length k? why is it not mentioned in the answer? $\endgroup$
    – nene4496
    Jun 7, 2020 at 15:24

Your Answer

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

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