[MUSIC] We have had a warmup exercise by designing an true approximation for the simple Steiner tree problem. Now let us dig into the real difficulty of this chapter and study the Steiner forest problem in full generality. As a reminder, our input, in addition to the graph with edge weights has sets of terminals S1, S2, S3, and so on. And we want to output a set of edges of minimum cost such that all the terminals in the same set Si are connected to one another for every set Si. So now we want an integer program to represent to model this problem, how do we do this? Let's take the specification of the problem line by line. We want a set of edges, how do we represent a set of edges? We know how to do this. We're going to have a variable xe 0 or 1 for every edge, 1 if we take it, 0 if we do not take it. We want an output of minimum cost. Easy, sum over e of c sub e and x sub e. This is the usual thing. For every set Si, for every pair of vertices, terminals u and v in Si we want them to be connected. Constraint for every i, for every terminal u and v in Si, how are we going to write the fact that u and v should be connected? Here is a way that will work well for our purpose here. Here is the graph g. Here are two terminals u and v. This is the red set. And here is a connection between u and v. What does it mean that u and v are connected? There's a path from u to v. Equivalently, we can say that if u and v are connected then every cut separating u from v must be crossed. A set of a Gs must cross every cut separating u from v. And that we can express with the linear constraint in the G program. What is a cut? A cut is a subset of the vertices such that if it's set for its u from v it contains exactly one of u and v. Either it contains only u and or it contains only v. That's a cut, S. Delta of S, the set of edges in the cut are all the edges that have one endpoint in S and the other one in V-S. So what does it mean that every cut is crossed? It means that among all these edges, at least one must be used by the path from u to v. And this we know how to write with a linear constraint. The sum of X sub e, for every e in delta of S must be at least 1. So that's our connectivity constraint. S, capital S, is the set of all cuts between terminals of the same sets. That is, it's the set of every set S of vertices such that there exist a set of terminals Si, there exist two terminals u, v, in Si, such that S separates u from v. Okay. And now we want to minimize the sum over e of ce xe such that for every S in our set, capital S of cuts, the sum of x sub e over delta of S is at least one and x sub e must be 0,1. This is an integer program for the standard forest problem. What is the linear program relaxation? It is the same thing replacing x sub e in {0, 1} by x sub e greater than or equal to 0. So that is the linear programming relaxation that we are going to use for the Steiner forest problem. If you look at this, you might make a worrisome observation. How many variables do we have? One for each edge of the graph m. How many constraints do we have? One for every subset of vertices separating some terminal from some other terminal in the same Si. How many constraints does that make? Many, too many, an exponential number of constraints. Is this worrisome? It would be if we were using the technique seen in the first part of this course of linear programming relaxation and randomized rounding. However, now we're doing a primal dual algorithm. Therefore, we do not need to solve this linear program explicitly. This linear program, does not need to be solved. We just need to construct a feasible solution and a feasible solution to the dual that will be related. Nevertheless, imagine we wanted to solve this linear program, we could still do it. We could still do it because actually even though it has an exponential number of constraints, we could still check whether a given x satisfies these constraints. This would be a good exercise. However, we're going to proceed with this linear programming relaxation for Steiner forest, and next, we will start constructing the dual.
