in Algorithm Design Manual - Solutions, Doing Books

The Algorithm Design Manual: Chapter 6

6-3. Assume that all edges in the graph have distinct edge weights (i.e. , no pair of edges have the same weight). Is the path between a pair of vertices in a minimum spanning tree necessarily a shortest path between the two vertices in the full graph? Give a proof or a counterexample.

Solution Let’s start with an example.

Our minimum spanning tree is marked by the thick edges. We are interested in the path between B and D. We’re interested in the weight b. If b is smaller than 5, the MST (minimum spanning tree) isn’t the shortest path. Would this change our MST? It depends. We could form the graph from B -> D -> C instead of B -> C -> D. It would be our MST if b + 3 < 2 + 3, i.e. e \in [0, 2] \setminus \{1, 2\}. In conclusion, the MST isn’t the shortest path if 2 < b < 5.

6-6. Suppose we are given the minimum spanning tree T of a given graph G (with n vertices and m edges) and a new edge e = (u, v) of weight w that we will add to G. Give an efficient algorithm to find the minimum spanning tree of the graph G + e. Your algorithm should run in O(n) time to receive full credit.

Solution

We are interested into each path going from u to v. In this example there is the initial path u->t->v and the new one u->v. Now we can check which one is shorter and take this one. The rest of the tree isn’t affected by this.

6-7. (a) Let T be a minimum spanning tree of a weighted graph G. Construct a new graph G′ by adding a weight of k to every edge of G. Do the edges of T form a minimum spanning tree of G′? Prove the statement or give a counterexample.

(b) Let P = {s, . . . , t} describe a shortest weighted path between vertices s and t of a weighted graph G. Construct a new graph G′ by adding a weight of k to every edge of G. Does P describe a shortest path from s to t in G′? Prove the statement or give a counterexample.

Solution (a) The order of the weights aren’t affected by the addition therefore it still forms the MST: a + c < b + c = a < b.

(b) No, see the counter example in the comments by Matus Goljer. Thanks for that!

6-23. Arbitrage is the use of discrepancies in currency-exchange rates to make a profit. For example, there may be a small window of time during which 1 U.S. dollar buys 0.75 British pounds, 1 British pound buys 2 Australian dollars, and 1 Australian dollar buys 0.70 U.S. dollars. At such a time, a smart trader can trade one U.S. dollar and end up with 0.75 × 2 × 0.7 = 1.05 U.S. dollars—a profit of 5%. Suppose that there are n currencies c1 , …, cn and an n × n table R of exchange rates, such that one unit of currency ci buys R[i,j] units of currency cj. Devise and analyze an algorithm to determine the maximum value of

R[c1, ci1] · R[ci1, ci2] · · · R[cik−1, cik] · R[cik, c1]

Solution Here’s the example as a graph.

The first problem is that maximum path algorithms don’t multiply the values the add them. This problem can be solved by using logarithms: \log(a \cdot b \cdot c) = \log(a) + \log(b) + \log(c).

EDIT: Please see the entry in the comments. Thanks

Write a Comment

Comment

  1. Can you work out the solution for the following Chapter 6 related problems:

    Is the path between a pair of vertices in a minimum spanning tree necessarily a shortest path between the two vertices in the full graph? Give a proof or a counterexample.

    When a vertex and its incident edges are removed from a tree, a collection of subtrees remains, as in the example below:
    Prove that there exists a vertex v whose removal leaves no subtree with more than n/2 vertices.
    Give a linear-time algorithm that, for any tree with n vertices, finds a vertex whose removal leaves no subtree with more than n/2 vertices. (*)
    problem

    • Hey, at least I can try:

      Is the path between a pair of vertices in a minimum spanning tree necessarily a shortest path between the two vertices in the full graph? Give a proof or a counterexample.

      Generally, no. For example take this graph and its minimum spanning tree:
      MST
      The shortest path in the full graph from A to C is 9 but the shortest path on the MST is 10.

      When a vertex and its incident edges are removed from a tree, a collection of subtrees remains.
      Prove that there exists a vertex v whose removal leaves no subtree with more than n/2 vertices.
      Give a linear-time algorithm that, for any tree with n vertices, finds a vertex whose removal leaves no subtree with more than n/2 vertices.

      You are basically looking for bridges. There’s also an algorithm on the page which works faster in this case because the tree is already a spanning tree. Hope that helps.

  2. Hi,

    Thanks for the solutions.

    Regarding exercise 6.23, I think that we need to find a cycle instead of a path (i.e. at the end, we need to convert back to the original currency achieving max profit).

    Also, could you please explain to me why applying the function 1/(1+e^w) to every weight does not change the shortest path?

    Thanks

    • Hi!
      Thanks for your comment. I think you’re correct.
      Then it’s sadly NP-hard because we don’t have a directed acylic graph anymore: http://en.wikipedia.org/wiki/Longest_path_problem

      I’m really glad for your comment because I know that a lot of people read this stuff and I don’t really have time anymore to recheck all the answers.

      Thank you

      • You can take the -log value of each R[i,j], then look for negative cycles (which after Floyd-warshall initialized with R[i,i] = infinity finishes you can read off from the diagonal). To reconstruct the conversion rate, just reverse the -log operation.

  3. The answer to the problem 6-7(b) is incorrect, here’s a simple counter-example

    A ——- 6 ——-> B
    \-1->C-1->D-1–/

    Now add k = 20 to each edge. The original shortest path (A->C->D->B) now has weight 63, while the optimal path is 26 (A->B).

    The issue here is that the constant k accumulates in the calcululation (for a path of length n, you are adding n TIMES k to its new overall weight).

    It works when constructing the spanning tree because there the path weights don’t matter