[MUSIC] Before we start this Steiner forest problem, let us first, as a warm up, study the Steiner tree problem. The Steiner tree problem. Look at this graph. Observe that if the subset of terminal consists of all nodes in the graph, then what you want to do is to connect all nodes to one another with a minimum cost set of edges. What is that? That is exactly the minimum spanning tree problem. So there's a special case of Steiner tree that is well known polynomial time minimum spanning tree. Namely, in the case of the graph of this example, how do you solve it? By Kruskal's algorithm for example, you solve the edges by order of increasing weight. And then you take edges one by one and add them to the tree if they don't create a cycle. 1, 2, this 3 create a cycle, you don't add it. 3, 4, this 5 creates a cycle, you don't add it. 5, 5, 6 creates a cycle, you don't add it. This 7 creates a cycle and then you're done. You have a tree spanning all vertices. So that is your minimum spanning tree, very easy polynomial time algorithm. I'm reminding you of this because this is something we're going to use as a sub routine for our approximation algorithm for Steiner tree. Here is a Steiner tree approximation algorithm. We have our input graph with some red vertices are terminals that we want to connect. What do we do with this? First we define a new graph. A new graph whose vertex set consists only of the red terminals. It does not have six vertices but only four vertices. And with edges correspond to paths in the original graph. So the edge set will be the complete graph. The edges will be weighted with an edge weight that is equal to the length of the shortest path between the two terminals in the original graph. For example, between these two terminals, the shortest path has length 5. Therefore, this edge has length 5. Or between this vertex and that one, the shortest path has length 7, so this edge has length 7. So that's the first step. Given a graph, given a set of terminals, define a new graph whose vertex set is the collection of terminals. Whose edges are the complete graph and whose weights are the length of the shortest path in the original graph. Next, I said we know how to use MST. Let's do MST. Compute the minimum spanning tree on the new graph. In this case, 3, 5, 6, there you go. You have the minimum spanning tree of this new graph. That's the second step. Three, translate this back to a tree in the original graph. Output the corresponding set of original edges. This 5 came from the path 2 plus 3. That 6 came from a path 2 plus 2 plus 2. That 3 came from a path or an edge of length 3. So you output the union of all these edges. In this particular case, the output has value 12. The optimal Steiner tree would have value 11. You would not use this edge of length 3, but that edge that has length 2. So this algorithm is not optimal. However, it does connect all the terminals, and it has a length that we're going to bound in a minute. And it's polynomial time because defining the new graph take polynomial time and the MST algorithm runs in polynomial time. So all that remains to do Is to analyze the cost of the output and bound it compared to the optimal cost. Okay, so to recap the algorithm. 1, a new complete graph on the subset of vertices. 2, minimum spanning tree on that graph. 3, output the corresponding set of original edges. The theorem is that this algorithm gives you a 2-approximation for the Steiner tree problem. So let me give you a proof of this theorem. We want to relate the value of the output to the value of OPT. Let us start from the unknown optimal tree. Here's your graph G. Here are terminals, in this case, four terminals in this graph. Here is the unknown optimal structure connecting those terminals to one another, unknown OPT. What are we going to do with this? How are we going to relate this to the value of the object constructed by the algorithm? First we go around the optimal tree to define some paths, more specifically double up every edge of the optimal tree. What you have is a connected graph where every vertex now has even degree. What is a graph that is connected and with all even degree vertices? It's an Eulerian graph. What property do Eulerian graphs have? There exists an Eulerian cycle. There exists a cycle that visits every edge of the graph or of the multigraph. So if you go through that particular cycle then what you have is a collection of terminal to terminal paths. So what you can get is something of that type that I am showing here. I go around the optimal tree twice, and in this case, I start from here, follow these edges to there. Follow those edges back here, then I go to this terminal, follow those edges back here, back down to this new terminal. And finally, follow these edges on that yellow path, whoo, to go back to the original terminal and then I'm done. Okay, so I have four terminal to terminal paths here. Purple, blue, green and yellow. Black, green and yellow. So now what? Now, these paths can be mapped to edges of the new graph, the graph that has one vertex for each terminal. The purple path maps to the edge from this terminal to that terminal. The black path maps to an edge from this terminal to that terminal. The green path maps to a green edge from this terminal to that one, and the yellow path maps to a path from this terminal to that terminal. What can we say about the sum of the path lengths? We traversed every edge twice exactly twice. So the total length is exactly two times the length of the tree we started from. We started from the tree whose length was OPT, an optimal tree. So the sum of the length of the paths is 2 times OPT. Now, if we remove any one of those edges, what we get is a tree. So, what this means is that there's a tree, this tree is longer, at least as long as the minimum spanning tree. The cost of this tree is at least the MST cost. So 2 OPT is at least the MST cost. And so to recap, the output of our algorithm is a set of edges with cost at most the cost of the MST, which is less than the cost of 2 OPT. And that proves that the algorithm is a 2-approximation. We now have a 2-approximation algorithm for Steiner tree. Let's take a little break from a proof and think about the history of the problem. Where does the Steiner tree problem come from? The name is because of Jakob Steiner, who was a 19th century German mathematician. The problem came to the attention of a number of mathematicians with the publication of a 1960s paper by Pollak and Gilbert, where they talked in particular about the geometric properties of a Steiner tree. They were interested in the case where the terminals are points in the Euclidean plane, and the graph consists of all possible vertices in the Euclidean plane, and the length is the Euclidean distance. Then you can see the very funny structure with these angles, 120 degree angles. And this is one page from the paper where they show the structure of some optimal Steiner trees. It's also in that paper that they presented the true approximation that we just discussed. In computer science, when was the problem discussed? This person is familiar. Richard Karp, we have mentioned it several times in this course already. What do we know about Richard Karp? In the early 1970s, he wrote a famous paper where he proved that many standard combinatorial optimization forms are NP-complete. Well, Steiner tree, the decision version of Steiner tree was one of them. So it's his responsibility if the problem cannot be solved in polynomial time. Worst than that Marshall Bern, Paul Plassmann made it even worse. They proved that the problem cannot be approximated. If p is different from np, then you cannot hope to get an approximation better than about 1.1%, 1 plus 1%. So, what we want to do is get a good constant factor approximation, that is the best we could hope for. And let me just mention a recent beautiful result. I will not prove it here but I just want to mention the current research on the problem. We have shown a 2-approximation. The current best is 1.39. There's a 1.39 approximation for the Steiner tree problem due to Byrka, Grandoni, Rothvoss, and Sanita. The problem was solved, this was presented in 2010. This is from only five years ago. This is current research. And, the technique is Iterated randomized rounding of a linear programming relaxation. So it's quite relevant to this course, but too sophisticated for the current course, but after taking it, maybe you'll be curious to go and look it up and try to understand it. For now, what we will try to do is, we will go from Steiner tree to Steiner forest, and design a 2-approximation for a Steiner forest with the primal-dual algorithm.