Question

Write the proof that the given problems are in NP (not NP-complete yet)

Longest Path
INSTANCE: Graph G = (V, E), positive integer K <= |V|.
QUESTION: Does G contain a simple path (that is, a path encountering no vertex more than once) with K or more edges?

Answer 1

For the correctness of Dijkstra, it is sufficient to show that d[v] = δ(s, v) for every v ∈ V when v is added to s. Given the shortest s ❀ v path and given that vertex u precedes v on that path, we need to verify that u is in S. If u = s, then certainly u is in S. For all other vertices, we have defined v to be the vertex not in S that is closest to s. Since d[v] = d[u] + w(u, v) and w(u, v) > 0 for all edges except possibly those leaving the source, u must be in S since it is closer to s than v. It was not sufficient to state that this works because there are no negative weight cycles. Negative weight edges in DAGs can break Dijkstra’s in general, so more justification was needed on why in this case Dijkstra’s works.