Homework 5: Graph Algorithms (Part II) & NP Completeness

Description

In this homework, we will focus our attention to finding shortest-paths and maximum flow on graphs, and NP Completeness.

Problem 1: Shortest Path 40 points

1. If p = fv₁; ; v_ng is the shortest path between v₁ and v_n, then prove that any subpath

p_ij = fv_i; ; v_j g in p is the shortest path between v_i and v_j . (20 points)

2. Write the pseudocode to find a negative weight cycle in a directed graph G = (V; E) with the weight function w : E ! R. (20 points)

Bonus Problem (20 points):

1. Demonstate Dijkstra’s algorithm on the following graph.

2. Implement Dijkstra’s algorithm in Python, and validate your code on the following graph.

1. Prove that there are uncountable number of unsolvable binary decision problems. Further-more, give an example of an unsolvable binary decision problem. (10 points)

2. Define NP, NP-Hard and NP-Complete classes, and give one problem in each of these com-plexity classes. (10 points)

3. Assuming that Hamiltonian circuit problem is NP-Complete, prove that traveling salesman problem is NP-Complete via reduction. (20 points)