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 = fv1; ; vng is the shortest path between v1 and vn, then prove that any subpath
pij = fvi; ; vj g in p is the shortest path between vi and vj . (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.
Part 5: Graph Algorithms (Part II) & NP Completeness
2
Problem 2:
Flow Networks
20 points
1. Define slack (residual flow) in an edge (u; v) 2 E in a the residual graph of a given graph G = (V; E). (10 points)
2. Demonstrate the Ford-Fulkerson algorithm on this following flow network, where each edge is labeled with its flow capacity. (10 points)
Bonus Problem (10 points):
Implement Edmonds-Karp algorithm in Python, and test your code on the given graph.
Part 5: Graph Algorithms (Part II) & NP Completeness
3
Problem 3:
NP Completeness
40 points
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)
