Hw10
1. You are given a graph G = {V,E} and its minimum spanning tree, MST(G), both in adjacency
list representation. Suppose that we wish to add a vertex v to G, along with some weighted edges
from v to other vertices in G. In other words we create a new graph, G′. Let MST(G′) be the
minimum spanning tree of G′. You may assume that all edge weights are distinct.
(a) Can any edge of G that is not in MST(G) end up in MST(G′)? Provide a clear proof.
(b) Your job is to produce MST(G′), given that G and MST(G) are already available.
Outline an algorithm, in English. Justify the time-complexity of your algorithm.
Answer:
Let G′ = {V ′, E ′}, where V ′ is equal to the union V and v, and E ′ is equal to the union of E and
all incident edges of v.
(a) Any edge e of G that was not part of MST(G) cannot become part of MST(G′).
We can prove this by contradiction. Suppose that the claim is false: e is part of MST(G′). Then
temporarily remove e to create two connected components of MST(G′). In other words, let e
define a cut, C, on MST(G′), partitioning its vertex set into subsets A and B. Now, which is the
lightest edge of E ′ to cross C? By the Cut Lemma, it must have been e, because it is the only edge
crossing C that is included in MST(G′). In other words if another edge in E ′ were lighter than e,
then it would have been in MST(G′) via the Cut Lemma. But now consider the cut on G that is
defined by vertex sets A and B, with v removed. We know that e crosses this cut because neither
of its endpoints is v. Also this cut is crossed by a subset of the edges that we just considered (i.e.,
all the edges incident to v are now missing), therefore e is still the lightest edge crossing this cut
on G and thus should have been in the MST of G; contradiction.
(b) Having established that the only edges that can be in MST(G′) are those from MST(G) or
new edges incident to v, construct a graph G∗ with vertex set V ′ and an edge set E∗ consisting
of all eligible edges just mentioned. All together there are V−1 edges in MST(G) and at most V
edges incident to v. In other words G∗ has O(V ) edges. Given the adjacency list of MST(G) it is
trivial to get the adjacency list of G∗ by introducing v and its edges, in O(V ) time. As we have
proved, MST(G∗) is equivalent to MST(G′), so we construct the former from scratch. The time
complexity is O(E∗ log V ′) = O(V log V ) time.
Note: it is possible to solve this problem in O(V ) time. You were not expected to do this. See
this link:
https://pdfs.semanticscholar.org/9956/30e37fcca240a50d09098666851ffe444df0.pdf
Hw11
1. Consider a one-dimensional intergalactic highway (let’s just model it as a horizontal line, on which
you can travel left or right). On the highway are n space stations. You’re currently at some
particular station, s, and want to get to another station, t, that is somewhere to the right of s.
To get from station to station, you must use privately owned teleportation services. Each owner
of a teleportation device is able to transport you between precisely one specific pair of stations (in
either direction), but nowhere else. There are m pairs of stations that are directly connected in
this way.
For each pair of stations, a, b, the owner of the teleport connector between a and b charges whatever
they like for a transfer. The amount is fixed, it doesn’t change over time. The amount charged is
not correlated to distance covered. You have full knowledge of all teleportation options and prices.
As everyone knows, because of the effect of teleportation on the human body, you can’t keep
switching directions when you teleport, unless you rest for a long time. In fact you can switch
directions at most once. You have no time to rest though, so you must get from s to t following
this constraint.
Algorithmically, how will you determine which path to take, so that the total price paid is mini-
mized? How fast can you compute / construct the best path?
Answer 1:
Create a directed graph with n vertices and m edges, where an edge from p to q denotes that it is
possible to teleport towards the right from station p to station q. Each edge is weighted by teleport
cost.
Compute SSSP with s as the source. All paths will have monotonically increasing x-coordinate.
Note that some vertices might not be reachable from s. Next, compute SSSP with t as the source.
Again, all paths will have monotonically increasing x-coordinate, so by reversing direction we will
have a shortest path from each vertex to t, with monotonically decreasing x-coordinate.
After running SSSP twice as described, for every vertex we add the two scores obtained. Keep the
overall minimum. This step takes O(n) time. What we have computed is the minimum cost path
among those that start at s, go towards the right, possibly overshoot t and turn around towards
the left, and end at t.
Now flip all edge directions and repeat. This will give all paths where we start at s, go to the left
to some position, and from there proceed only towards the right until reaching t.
All weights are positive because you must have some positive cost to teleport, so running Dijkstra’s
algorithm each time will work correctly. However, the type of graph that we create is a DAG so
we can run a topological sort and obtain all shortest paths in O(n + m) time instead of using
Dijkstra. Note that this is really O(m′) where m′ is the number of edges that can be found on
search starting from source or target.
Answer 2:
Start as in first paragraph of the previous answer, with a graph where all edges point to the right.
Then make a copy of the graph with all edges pointing to the left. Visualize the copy drawn on
a horizontal line underneath the original. Now connect each vertex on the top graph to its clone
directly underneath. Give each of these V edges a weight of zero. This entire graph is a DAG.
Now run SSSP from s in the top level. Compare the score of t (in the top level) to that of its clone
that is located in the bottom level. The score of t represents the best path that always goes to
the right from s to t. The score of the clone represents the best path that begins at s, overshoots
the position of t, eventually follows a vertical edge into the lower level, and then moves to the left
to the clone of t.
Now repeat by flipping the vertical edge directions to point from lower level to upper, and run
SSSP from the clone of s. That will allow us to consider paths that initially move to the left and
then turn around to go right to t.
Essentially the vertical edges between the two levels act as options for turning around. By con-
struction only one vertical edge can be chosen.