Description

Assignment 2
1. (25 points) Given a directed weighted graph G = (V,E,w) where edges can be negatively weighted and a vertex s, consider the execution of Bellman-Ford algorithm. Recall that the algorithm starts by initializing dist(s) = 0 and dist(u) = ∞ for each u ≠ s; and, at each iteration, the algorithm updates dist(v) ← min{dist(v),dist(u) + w(u,v)} for each edge (u,v).
(a) (10 points) In the class, we have proved that G contains a negatively weighted cycle if dist(u) is updated for some u ∈ V at the |V |-th iteration. In this subquestion, you are to complete the correctness proof of Bellman-Ford algorithm by proving the converse of this statement: if G contains a negatively weighted cycle, then there exists u ∈ V such that dist(u) is updated at the |V |-th iteration.
(b) (5 points) Give a counterexample to disprove the following claim: for a vertex t, if there is a path from s to t that contains a negatively weighted cycle, then dist(t) must be updated at the |V |-th iteration.
(c) (10 points) Adapt Bellman-Ford algorithm to solve the following problem. Give a vertex s and a vertex t, decide if there is an s-t path that contains a negatively weighted cycle. You need to prove the correctness of your algorithm. Your algorithm must run in time O(|V | · |E|).
2. (25 points) Given a directed graph G = (V,E), a starting vertex s ∈ V and a destination vertex t ∈ V . Design a polynomial time algorithm to decide if you can walk from s to t such that every vertex is visited. You are allowed to visit a vertex or an edge more than once. Prove the correctness of your algorithm and analyze its time complexity.

Page 1 of 2
3. (25 points) Let G = (V,E) be a graph and s be a vertex such that there is a path from s to each u ∈ V . We say G is a good graph if there exists a tree T = (V,E′) that share the same vertex set V with G such that T is both a depth-first search tree and a breadth-first search tree.
(a) (10 points) If G is an undirected graph, prove that G is a good graph if and only if G is a tree.
(b) (10 points) If G is a directed acyclic graph, prove or disprove that the vertex set V can be sorting in an array L such that L is both an ascending order of the distances from s and a topological order.
(c) (5 points) Prove or disprove the converse of (b). That is, if G is a directed acyclic graph where the vertex set V can be sorting in an array L such that L is both an ascending order of the distances from s and a topological order, then G is a good graph.
4. (25 + 5 bonus points) Given an undirected simple graph G = (V,E) and a vertex s, you need to find a cycle with the minimum length that contains s. A cycle cannot contain an edge more than once.
(a) (25 points) If G is unweighted, design an algorithm for this problem that runs in time O(|V | + |E|).
(b) (5 bonus points) If G is edge-weighted such that the weights are positive, design an algorithm for this problem that runs in time O(|V |2).
For both parts, you need to prove the correctness of your algorithms and analyze their time complexities.

Page 2 of 2