Description

Let G = (V,E) be an undirected graph with distinct non-negative edge weights. Consider a problem similar to the single-source shortest paths problem, but where we define path cost differently. We will define the cost of a simple s-t path Ps,t = {e1,e2,…,ek} to be

The cost of a path is now just the largest weight on that path, rather than the sum of the weights on the path. Give an algorithm that takes as input an undirected graph G = (V,E) with non-negative edge weights, and a vertex s ∈ V , and computes the path from s to every other node in G with the least cost under cost function c(·). That is, for each t ∈ V , find a simple path Ps,t = {(s,v1),(v1,v2),…,(vk−1,vk),(vk,t)} connecting s to t, such that, letting S denote the set of all simple paths connecting s and t, c(Ps,t) = minP∈S c(P).
Your algorithm should run in O(|E| + |V |log|V |) time. Prove the correctness of your algorithm and its runtime. Hint: note the similarities between Dijkstra’s algorithm and Prim’s algorithm.
1
2 Problem 2 (15 points)
You are given a simple weighted graph (no self-edges or multi-edges) G = (V,E) and its minimum spanning tree Tmst. Somebody added a new edge e to the graph G. Let’s call new graph G0 = (V,E ∪{e}). Devise an algorithm which checks if Tmst is also a minimum spanning tree for the graph G0 or not. Your algorithm should work in O(|V |) time. Prove correctness of your algorithm and provide running time analysis.
You can assume that all edge weights in G0 are distinct. Tmst and G0 are given to you as adjacency lists.
3 Problem 3 (20 points)
An airline has n flights. In order to avoid “re-accommodation”, a passenger must satisfy several requirements. Each requirement is of the form “you must take at least ki flights from set Fi”. The problem is to determine whether or not a given passenger will experience “re-accommodation”. The hard part is that any given flight cannot be used towards satisfying multiple requirements. For example, if one requirement states that you must take at least two flights from {A,B,C}, and a second requirement states that you must take at least two flights from {C,D,E}, then a passenger who had taken just {B,C,D} would not yet be able to avoid “re-accommodation”.
Given a list of requirements r1,r2,…,rm (where each requirement ri is of the form: “you must take at least ki flights from set Fi”), and given a list L of flights taken by some passenger, determine if that passenger will experience “re-accommodation”. Your algorithm should run in O(|L|2m) time.
Hint: You should just need to show how this can be reduced to a network flow problem and then use a blackbox algorithm solving the flow problem. Prove that your reduction is correct and that the runtime of the algorithm you use will be O(|L|2m) for the reduction you give.
2