The Exact Distance problem is: Given an edge weighted graph G = (V, E), a vertex

Question

The Exact Distance problem is: Given an edge weighted graph G = (V, E), a vertex v_k, and a distance D, is there a simple path from v_1 to v_k with length exactly D? The length of a path is the sum of the weights in the path. An edge weighted graph is a graph which has a weight w(e) assigned to each edge e elementof E(G). A simple path is a path which does not revisit any vertices or edges. (a) Prove that the Exact Distance problem is in NP. (b) Prove that the Hamiltonian Path problem reduces to the Exact Distance problem in polynomial time. (Note that proving a) and b) proves that the Exact Distance Problem is NP-complete.)

Explanation / Answer

We can prove exact distance problem is empty.

For this we need to prove the problem is NP.For that by choosing the solution we can figure it out we can verify the solution in polynomial time. My proof showed that we can verify the solution in O(ev) time, where e is the number of edges and v is the number of vertices.

Then we need to prove NP-complete can be reduced to the exact distance problem. For this

We can use Hamiltonian path problem. One thing we need to take careful while choosing that. We should know what is the inputs in the beginning of the program.

We can prove that Hamiltonian path reduces exact distance problem in the polynomial time

Consider a Hamiltonian graph H having vertices v. To create a new graph H we should assign weight to each edge so that the sum of the weighted edges from v to destination is equal to a distance R. Graph H has a Hamiltonian path if and only if graph H has a simple path from V to Vd with length exactly R. So that H can be find in polynomial time and we can say that it’s a polynomial reduction.

It consists of graph H, an edge e, and a length l.

The output is a cycle of length l containing e

The other out put will be true if a cycle exists, false otherwise.

There are two easy ways to prove it is NP-hard. Imagine you had a graph algorithm, Graph(H,e,l)

Reduce the Hamiltonian length.

Vertices refer D in graph H.

Consider a function given below.

Let f(H)=H=(D,e)

Consider edge as f1 and f2 (f1,f2).

F1 and f2 are connected to H.There distance computed in t time.

Let f1 and f2 has a degree of 2, and is only connected to fn.

H belongs to HP f(h)H

Consider some H.

Graph have f1,f2…fn.

H belongs to Hamiltonian path length H

So Hamiltonian path is np complete.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.