MPCS 55001 — Problem Set 6

Instructions

This problem set is due on Wednesday May 20, 2020 at 20:00 Central, to be submitted on Gradescope. Each problem is worth 10 marks in total.

Problems

  1. Give and prove a recurrence for the single-source shortest paths problem: Given a directed graph $G = (V,E)$ with an edge weight function $e: E \to \mathbb R$ and a source vertex $s$, find a shortest path from $s$ to $v$ for every $v \in V$.

    1. Consider $n$ cities each with their own bus system and fares. Each of these cities' transit authorities has been pretty good at local cooperation: if a city is directly reachable from another, it is possible to travel between the cities on the same fare. However, it is impossible to travel further than that without buying another ticket.

      This is obviously not ideal. A regional consortium was formed and decided to roll out universal fares to each city. Once a city has universal fares, anyone may travel through it on one fare.

      For example, consider the following region. At the beginning, no cities have any universal fares, so travel only occurs between adjacent cities.

      Universal fares are rolled out in the order indicated by the cities' numbers. City 1 gets universal fares first. Now, it is possible to travel from City 8 to City 2, via City 1. Then City 2 gets universal fares, and travel from City 3 to City 5 can occur, via City 1 and City 2.

      Once City 4 gets universal fares, residents of City 10 notice something interesting. Previously, it had cost 6 to travel to City 5, but once travel through City 4 became more convenient, people realized that travelling from City 10 to City 5 was cheaper by going through City 4 instead of directly.

      This leads some transit nerds to decide to cook up a website that will tell you the cheapest way to travel from city $i$ to city $j$ in phase $k$ of the universal fare rollout (i.e. when cities 1 through $k$ have universal fares).

      Given a list of $n$ cities labelled $1, \dots, n$ in the order that they are added to the universal fare program and costs for travel directly from one city to another (this may not be symmmetric), give and prove a recurrence for the minimum cost of travelling from city $i$ to city $j$ via only cities with universal fares if $k$ is the latest city to get universal fares.

    2. Give an algorithm is pseudocode for computing the weight of shortest paths between every pair of vertices in a given directed graph $G = (V,E)$ with edge weight function $w:E \to \mathbb R$, assuming $G$ does not contain any negative cycles (it can contain negative edges), in $O(|V|^3)$ time. Prove the correctness and efficiency of your algorithm.

  3. Let $G = (V,E,s,t,c)$ be a flow network with $|V| = n$, $|E| = m$, and a maximum flow $f:E \to \mathbb N$ which is acyclic, in that no cycle in $G$ has positive flow on all its edges. Suppose we choose an edge $e \in E$ and reduce its capacity by 1. Show how to find a maximum flow on the resulting graph in $O(m+n)$ time.