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$
0
$\begingroup$

Welcome to the site! Let $G = (V, E)$ be a undirected graph. If $G$ is Hamiltonian, then there exists a simple cycle $C$ in $G$ containing every vertex, i.e. the length of $C$ is $|V|$. Note that if you delete any edge $vw$ from $C$, you end up with a path of length $|V| - 1$ between $v$ and $w$. Conversely, if you find a simple path $P$ of length $|V| - 1$ between two vertices $v, w$ connected by an edge, you can add the edge $vw$ to $P$ to obtain a Hamiltonian cycle (as $P$ cannot contain $vw$ due to being a simple path). Also observe that the choice of $v$ and $w$ is arbitrary as long as they are connected by an edge.

So we can obtain the following reduction: Starting from some graph $G = (V, E)$, pick some edge $vw \in E$ and delete it to obtain a new graph $G' = (V, E \setminus \{vw\})$. Using the observations we made, it follows that $G'$ has a path $P$ between $v$ and $w$ of length $|V| - 1$ if and only if adding $vw$ to $P$ yields a Hamiltonian cycle in the original graph $G$. As $G'$ can be computed from $G$ in polynomial time, 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$
  • $\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 '20 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$ – Watercrystal Jun 6 '20 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$ – Watercrystal Jun 6 '20 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 '20 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 '20 at 15:24

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.