C H A P T E R 5 CUT PROBLEMS AND THEIR APPLICATION TO DIVIDE-AND-CONQUER David B. Shmoys Divide-and-conquer is one of the most basic techniques in the design and analysis of algorithms, and yet, until recently, there have been essentially no performance guarantees known for approximation algorithms based on this approach. This chapter will present approximation algorithms for several NP- hard graph-theoretic cut problems, and their subsequent application as a tool for the “divide” part of divide-and-conquer approximation algorithms for a wide variety of problems. INTRODUCTION 5.1 One of the most important paradigms in the design and analysis of algorithms is the notion of a divide-and-conquer algorithm. Every undergraduate course on algorithms teaches this method as one of its staples: to solve a problem quickly, one carefully splits the problem into two subproblems, each substantially smaller than the original, recursively solves each of these, and then pieces together the solution to each part into the overall solution desired. This approach has also been used in the design of heuristics for NP-hard optimization problems, but until recently, the heuristics designed in this way were either too complicated to analyze, or had extremely poor performance guarantees. In one of the most important breakthroughs in the design and analysis of approximation algorithms in the past decade, Leighton and Rao [LR88, LR94] devised an elegant approach for using 1 divide-and-conquer in a way that produced superior performance guarantees for a wide range of problems. The key ingredient to their approach is the design of approximation algorithms for certain cut problems. These algorithms, which are of independent interest, provide approximate max-flow min-cut theorems for multicommodity flow problems that are analogous to the famous max-flow min-cut theorem for (single-commodity) network flow of Ford and Fulkerson [FF56]. In this chapter, we will survey the techniques that were introduced by Leighton and Rao, as well as a number of advances that have been obtained subsequently in the area. Although the methods that we will describe are much more general, we shall first illustrate this approach on a concrete example, the minimum cut linear arrangement problem. Suppose that we are given an undirected graph G =(V,E) with n vertices, and we wish to lay out the graph on integer points of the real line; that is, for i =1,...,n,we assign one vertex to i, in such a way that each vertex is assigned to a value in this range; let σ(i)denote the vertex assigned to i, for each i =1,...,n. We can evaluate this layout in the following way: for each i =1,...,n, let Si denote the set of edges in E of the form (σ(j),σ(k)), where j ≤i and k > i; we wish to choose a layout so that maxi=1,...,n |Si |is minimized. More generally, in the weighted version of this problem, each edge e ∈E has a non-negative cost c(e) associated with it, and we wish to lay out the graph on the line so as to minimize maxi=1,...,nc(e). (5.1) e∈Si Let OPTLA(G) denote the optimal value. Figure 5.1 gives an instance of this problem, and feasible solution σ. The results of Leighton & Rao and are based on an algorithm for the graph bisection problem, which serves as the engine for the divide-and-conquer approach. In words, this is the problem of finding a minimum-cost subset of edges whose deletion separates the graph into two components of essentially equal size. More formally, we are given an undirected graph G =(V,E) where each edge e ∈E has a given non-negative cost c(e); once again, and throughout this chapter, we shall let n denote the number of vertices in the given graph. We wish to partition the vertex set into V1 and V2 such that |V1|= n/2 (and hence |V2|= n/2 ) so as to minimize c(e), where for any S ⊆V , δ(S) e∈δ(V1) denotes the set of edges {(u,v) =e ∈E : u ∈S,v ∈S}. Suppose that we have a ρ-approximation algorithm for the graph bisection problem: that is, the cost of the bisection found, B(G), is no more than ρ times the cost of the optimal bisection. This can be used to derive the following divide-and-conquer algorithm for the minimum cut linear arrangement problem. Apply the bisection algorithm to your input G to obtain V1 and V2; we shall lay out V1 on the set {1,2,..., n/2 }and lay out V2 on the set { n/2 +1,...,n}. Thus, we have divided the problem into two problems of half the size, and we recursively compute good layouts for the graphs induced by V1 and V2, which we call G1 and G2, respectively. Of course, when there is only one vertex to be laid out, there is no need for further recursion. How good is this divide-and-conquer algorithm for the minimum cut linear arrangement problem? Let A(G) denote the objective function value of the solution produced by this algorithm on input G. We will show that A(G) =O(ρlogn)·OPTLA(G) for any graph G; that is, it is a O(ρlogn)-approximation for the minimum cut linear arrangement problem. Consider the top level of the recursion: the edges of the graph G can be 5.1 INTRODUCTION 3 partitioned into three sets: the edges of G1, the edges of G2, and the edges in δ(V1); the graphs G1 and G2 are independent problems in the sense that in evaluating the objective function value (5.1) of a layout, for i =1,..., n/2 , none of the edges in G 2 are relevant, and for i = n/2 +1 ,...,n, none of the edges in G 1 are relevant (see Figure 5.1). More precisely, each subset of edges Si , i =1,..., n/2 can be partitioned into two subsets: those in G1 and those in δ(V1) and hence the total cost of those edges can be bounded by A(G1)+B(G). For each subset Si , i = n/2 +1 ,...,n, the total cost of these edges can be similarly bounded by A(G2)+B(G). Hence, A(G)≤max{A(G1),A(G2)}+B(G). σ(i) i 4 edges in G1 edges in bisection edges in G2 1 23 567 8 S5 edges in S5 maxi=1,...,9 |Si |=7 FIGURE 5.1 An instance of the minimum cut linear arrangement problem Observe that we can construct a bisection from any linear arrangement σ: let V1 and V2 be, respectively, those vertices mapped by σ to values no more than n/2 and those mapped to values greater than n/2 . The cost of the linear arrangement σ is, by definition, at least the cost of this bisection. Consequently, the cost of the optimal bisection is at most OPTLA(G), and hence the bisection used in the algorithm has cost B(G) ≤ ρOPTLA(G). But this implies that A(G) ≤max{A(G1),A(G2)}+ρOPTLA(G). (5.2) It is easy to see that this implies the claimed performance guarantee. With each level of recursion, the size of the relevant graphs is reduced by a factor of 2. Hence, there are logn levels of recursion (unless explicitly noted, any logarithm in this chapter has base equal to 2). With each level of recursion, we incur a cost of ρOPT LA(G¯) for some sub ¯ graph G of G; clearly, OPTLA(G¯)≤OPTLA(G). Hence, A(G)=O(ρlogn)·OPTLA(G). A straightforward inductive argument can be used to write out a more formal proof. In fact, this analysis did not require that we find a near-optimal bisection. It would have been sufficient to produce a partition in which, say, both V1 and V2 have at most 2n/3 vertices. So if we can produce such a balanced cut for which the cost c(e) e∈δ(V1) is within a factor of ρ of the optimal bisection cost, then we could still apply the same analysis. This is precisely what Leighton & Rao did: they gave an algorithm that produced a balanced cut of cost within a factor of O(logn) of the optimal bisection cost. Consequently, they obtained an O(log2 n)-approximation algorithm for the minimum cut linear arrangement problem. In Section 5.5 we will discuss a variety of balanced cut theorems and their application to several different optimization problems. It is important to note that this framework for obtaining approximation algorithms by divide-andconquer was proposed by Bhatt & Leighton [BL84], who focused attention on designing an approximation algorithms for the graph bisection problem. We shall next try to motivate the mathematical ideas underlying Leighton & Rao’s algorithm to find a good balanced cut. The balanced cut problem seems superficially related to the minimum (s,t)-cut problem, where one is given a graph and two specified nodes s,t ∈V , and wishes to find a minimum-cost subset of edges whose deletion disconnects the nodes s and t. One of the most fundamental results in combinatorial optimization is the max-flow min-cut theorem of Ford and Fulkerson [FF56], which states that the total cost of the minimum cut is exactly equal to the maximum flow value in the graph between s and t. In the latter problem, flow may be shipped along any path between s and t, and the aim is to maximize the total flow shipped, subject to the constraint that for each edge e ∈ E, the total flow shipped on paths that contain e is at most c(e). It is easy to see that for any flow and any cut, the value of the flow can be no more than the total cost of the cut. Ford and Fulkerson gave an algorithm that simultaneously constructed a flow and a cut of equal value, and hence each is an optimal solution to its respective optimization problem. The balanced cut problem is more closely related to a so-called multicommodity generalization of the maximum flow problem. In multicommodity network flow problems, there are k pairs of terminals (si ,ti ), i =1,...,k, and the edge capacity c(e) limits the total flow, over all commodities, that can be shipped through edge e, for each e ∈ E. There are two variants of this problem that we will consider. In the maximum multicommodity flow, we simply want to maximize the total amount that is shipped between pairs of terminals. In the maximum concurrent flow problem, there is a specified demand d(i), 5.2 MINIMUM MULTICUTS AND MAXIMUM MULTICOMMODITY FLOW 5 for each commodity i = 1,...,k. One might ask: can we find a feasible solution in which the total flow between si and ti is at least d(i), for each i = 1,...,k? In the maximum concurrent flow problem, we wish to maximize λsuch that the demands λd(i), i = 1,...,k, can be met. It is common to view the single-commodity max-flow min-cut theorem as having two parts: the weak duality theorem, which states that, for any instance, the maximum flow value is at most the minimum cut capacity, and the strong duality theorem, which states that, for any instance, there exists a feasible flow and a feasible cut for which their objective function values are equal. It is easy to obtain generalizations of the weak duality theorem in these multicommodity settings: for any instance, the maximum multi- commodity flow value is at most the optimal value of the minimum multicut problem, and the maximum concurrent flow value is at most the optimal value of the sparsest cut problem. Unfortunately, the strong duality theorem does not generalize to either of these pairs of problems. Furthermore, whereas both multicommodity generalizations of the flow problem can be solved (via linear programming algorithms) in polynomial time, the minimum multicut and sparsest cut problems are NP-hard. (In contrast, the variants of these multicommodity flow problems in which we restrict attention to integer-valued flows in NP-hard.) Leighton & Rao [LR88] gave an approximate multicommodity max- flow min-cut theorem, by giving an algorithm that finds a feasible concurrent flow and a corresponding sparse cut for which the objective function values are within a logarithmic factor of each other. Consequently, this algorithm is an approximation algorithm for the sparsest cut problem with a logarithmic performance guarantee. This algorithm can be adapted to yield the approximation algorithm for the balanced cut problem that was claimed above, in the discussion of the minimum cut linear arrangement problem. The work of Leighton & Rao provided an exciting starting point for research on approximation algorithms for cut problems and their application to divide-and-conquer algorithms for other types of problems. Furthermore, their techniques for cut problems have subsequently been applied directly to other problems, such as the feedback arc set problemindirectedgraphs;adivide-and-conquerapproachisstill employed,butthe“divide” part of the algorithm exploits the structure of the problem at hand to obtain a superior performance guarantee. In this chapter, we shall try to highlight some of the algorithmic techniques that have been developed in this area, and give an overview of the results that have been obtained. MINIMUM MULTICUTS AND MAXIMUM MULTICOMMODITY FLOW 5.2 In this section, we will consider the minimum multicut problem and the maximum multicommodity flow problem for undirected graphs. We shall see that these problems are closely related, and we shall exploit this relationship to derive an approximation algorithm for the cut problem. 5.2.1 MULTICUTS, MAXIMUM MULTICOMMODITY FLOW, AND A WEAK DUALITY THEOREM Given an undirected graph G =(V,E)and k pairs of vertices (s1,t1),...,(sk ,tk ),a multicut is a subset of edges F ⊆ E, such that if all edges in F are deleted, none of the pairs (si ,ti ), i =1,...,k, are in the same connected component in the remaining graph ¯ G =(V,E −F). In the minimum multicut problem, we are also given a positive cost c(e) for each edge e ∈ E, and we wish to find the multicut of minimum total cost. We shall let m denote the number of edges, |E|. Let Pi denote the set of all paths between si and ti , i =1,...,k. The minimum multicut problem can be stated as the following integer linear programming problem: minimize e∈E c(e)x(e) (5.3) subject to e∈P x(e)≥1, x(e) ∈{0,1}, for each P ∈Pi ,i =1,...,kfor each e ∈E. , (5.4) (5.5) It is easy to see that if k =1, then this problem reduces to the traditional minimum (s,t)-cut problem in undirected graphs. Unfortunately, the more general problem is NP- hard [DJP+92], and hence we shall consider approximation algorithms for it. Just as the optimization algorithm for the minimum (s,t)-cut is based on solving a maximum (single-commodity) flow problem, we shall derive an approximation algorithm for the multicut problem that is based on solving a maximum multicommodity flow problem, which is dual to it. The maximum multicommodity flow problem is as follows: given an undirected graph G =(V,E), where each edge e ∈E has an associated positive capacity c(e), and k pairs of terminal vertices, (si ,ti ), i =1,...,k, assign a flow value f (P) to each path P ∈Pi , i =1,...,k, so that, for each edge e ∈E, the total flow value assigned to paths that contain this edge is at most c(e). The aim is to maximize the total flow between all of the given pairs of vertices. Let Pi (e)denote the set of all paths between si and ti that contain edge e; that is, Pi (e)={P : e ∈P,P ∈Pi }, i =1,...,k. This problem can be formulated as the following linear programming problem. k maximize f (P) (5.6) i=1 P∈Pi subject to k f (P)≤c(e), for each e ∈E, (5.7) i=1 e∈Pi (e) f (P)≥0, for each P ∈Pi , i =1,...,k. (5.8) Note that in this case, we do not require that the variables be restricted to integer values, i.e., it is a linear programming problem, not an integer linear programming problem. The reader should note that the same input is required for both the maximum multi 5.2 MINIMUM MULTICUTS AND MAXIMUM MULTICOMMODITY FLOW commodity flow problem and the minimum multicut problem. We shall argue next that, for any such input, if we consider any multicut and any feasible multicommodity flow, then the total flow value is at most the cost of the multicut; that is, the weak duality theorem for single-commodity case generalizes to this setting. Consider any unit of flow that uses the path P between si and ti . The multicut must contain at least one of edges in this path P. As in the single-commodity case, we can view the total cost of a cut as the capacity of this cut. Thus, each unit of flow of the total multicommodity flow “uses up” at least one unit of the total capacity of the multicut, which implies the claim. Hence, we have obtained the following weak duality theorem. LEMMA 5.1 For any input to the maximum multicommodity flow and the minimum multicut problems, the total flow value of any feasible flow is at most the cost of any multicut. 5.2.2 FRACTIONAL MULTICUTS, PIPE SYSTEMS, AND A STRONG DUALITY THEOREM Garg, Vazirani, & Yannakakis [GVY93] give an approximation algorithm for the minimum multicut problem that first solves the linear relaxation of (5.3)-(5.5), in which the constraints (5.5) are replaced by x(e)≥ 0, for each e ∈ E, (5.9) and then uses this optimal fractional multicut to guide the search for a good (integer) multicut. Consequently, it is useful to have a good understanding of this linear relaxation. Feasible solutions to the linear relaxation (5.4) and (5.9) have a natural physical interpretation. For each edge e ∈ E, one can view its decision variable x(e)as specifying the length of edge e. From this perspective, the constraints (5.4) can be described as requiring that the edge lengths have the following property: for each path P between si and ti , the total length of P is at least 1. Equivalently, we could require that the length of the shortest path between si and ti is at least 1. What physical interpretation does this imply for the objective function? The contribution of each edge e ∈ E to the objective function is c(e) times its length. Suppose that we view the graph as a system of pipes, where the edges correspond to the pipes themselves, and the vertices correspond to junction points at which the pipes meet. In this case, if we interpret c(e)as the cross-section area of the pipe corresponding to the edge e, then c(e) times its length is exactly equal to the volume of this pipe, and the overall objective function is the total volume of the pipe system. So the linear relaxation is to find the minimum-volume pipe system for the input in which si and ti are at least 1 unit apart from each other, for each i = 1,...,k. The linear program for the maximum multicommodity flow problem, (5.6)-(5.8), is the dual linear program of minimum fractional multicut problem, (5.3), (5.4), & (5.9). To reinforce our intuition about these linear programs, we shall argue directly that any feasible length function for the pipe system gives an upper bound on the total value of any feasible multicommodity flow. Consider any unit of flow that uses the path P between si and ti . This unit of flow “uses up” e∈Px(e)units of volume. However, we have constrained this sum to be at least 1; that is, each unit of flow sent between an (si ,ti )pair con sumes at least one unit of volume. Hence, the total flow value is at most the total volume of the pipe system. Of course, the strong duality theorem of linear programming states that the optimal value of the primal is equal to the optimal value of the dual, provided that an optimal solution exists (see, for example, Chv´atal [Chv83]); hence, the minimum feasible pipe-system volume is equal to the total value of the maximum multicommodity flow. 5.2.3 SOLVING THE LINEAR PROGRAMS We have already indicated that the approximation algorithm of Garg, Vazirani, & Yannakakis will first find an optimal fractional multicut. As presently stated, this might appear to be a daunting task, since the size of this linear program is exponential. However, we shall argue that one can still find an optimal solution in polynomial time, and that there are a number of approaches to doing so. Perhaps the simplest approach is to observe that both the minimum fractional multi- cut problem and the maximum multicommodity flow problems have equivalent formulations that are of polynomial size. We first consider the maximum multicommodity flow problem. We define a flow variable fi (e)for each commodity i =1,...,k, and each edge e ∈ E. For each vertex v∈V −{si ,ti }, we require that the total flow of commodity i into v is equal to the total flow of commodity i out of vertex v. For each edge e ∈ E, we require that the total flow (in both directions) on e over all commodities is at most c(e). The total flow of commodity i is computed by considering the net flow of commodity i out of vertex si , and the objective function is, as before, the sum of these totals over all commodities. It is not hard to show that this more compact linear program is equivalent to (5.6)( 5.8). The more compact version has O(km) variables and O(m +kn) constraints, and hence can be solved in polynomial time, using any polynomial-time linear programming algorithm (e.g., that of Khachiyan [Kha79] or Karmarkar [Kar84]). Furthermore, this optimal solution can be converted, in polynomial time, to an optimal solution to the linear program (5.6)-(5.8) by standard “flow decomposition” methods (see, e.g., Ahuja, Magnanti, & Orlin [AMO93]). Hence, we can find an optimal solution to the maximum multicommodity flow problem in polynomial time. If we consider the dual linear program of this more compact formulation of the maximum multicommodity flow, then we obtain a linear program equivalent to (5.3), (5.4), & (5.9). In fact, we can easily compute an optimal pipe system from the optimal primal and dual solutions to the compact formulation: set x(e), the length of edge e,to bethe optimal value to the dual variable corresponding to the primal constraint that the total flow on edge e is at most c(e). Another option is to rely on the nature of the first polynomial-time algorithm for linear programming, the ellipsoid algorithm. One of the most important features of this algorithm is that in order to obtain a polynomial-time algorithm for a linear program with an exponential number of constraints, we need only provide a polynomial-time subroutine that, given a solution x, either proves that x is feasible, or else finds a violated constraint (see, for example, Gr¨otschel, Lov´asz, & Schrijver [GLS88]). This subroutine is said to solve the separation problem for this linear program. For the minimum fractional 5.2 MINIMUM MULTICUTS AND MAXIMUM MULTICOMMODITY FLOW 9 multicut problem, given by (5.3), (5.4), & (5.9), the subroutine required is just a shortest- path procedure: we need to verify that the length (with respect to x) of the shortest path between si and ti is at least 1, for each i = 1,...,k. Either we have identified an (si ,ti ) pair for which the length of the shortest path is less than 1, in which case this shortest path corresponds to a violated constraint, or else we have shown that the current length function is feasible. Hence, the ellipsoid algorithm can be used to solve our (exponential- sized) linear program in polynomial time. Finally, we will see that a nearly-optimal length function would work essentially as well in finding a good multicut. There has been a sequence of results obtained in designing fully polynomial approximation schemes for the maximum concurrent flow problem and other related problems. The goal of this line of research is to design algorithms that take advantage of the combinatorial structure of these problems (as opposed to a general purpose LP algorithm) in order to obtain more efficient algorithms, albeit with the disadvantage of finding solutions of objective function value within a factor of (1 + )of optimal. It is important to note that unlike for other problems that we have been discussing here, these approximation schemes are for problems solvable in polynomial time. Since we are losing a logarithmic factor in finding a multicut from the LP solution, it makes sense to relax our aim to finding a near-optimal LP solution, especially since this appears to be an easier computational problem. Shahrokhi & Matula [SM90] have proposed a combinatorial algorithm for a rather special case of the maximum concurrent flow problem that delivers a flow of objective function value within a factor of (1 + ) of optimal in time bounded by a polynomial in the size of the graph and 1/ . The key to analyzing the running time of this algorithm is an exponential potential function, which has been the basis for several subsequent papers as well. Klein, Plotkin, Stein, & Tardos [KPST94] and Leighton, Makedon, Plotkin, Stein, Tardos, & Tragoudas [LMP+95] subsequently improved and extended this result to derive an algorithm for the maximum concurrent flow problem for which the running time for a k-commodity problem is competitive with the running time for k single- commodity maximum flow computations. This was generalized by Plotkin, Shmoys, & Tardos [PST95] to yield a fully polynomial approximation scheme for a wide range of combinatorially defined linear programming problems, called fractional packing and covering problems. Results similar to those in [PST95] were independently obtained by Grigoriadis & Khachiyan [GK94]. We will explain the main ideas behind the framework proposed in [PST95] and show how it can be applied to the problem of computing a maximum multicommodity flow. A fractional packing problem is a linear programming problem of the following form: for a given matrix A ∈ m×n and vector b ∈ m , we wish to minimize λsubject to Az ≤ λb, z ∈ Q, where Q is a polytope such that Az ≥ 0 for each z ∈ Q. The idea of the algorithm is that Q is supposed represent “easy” constraints, and that Az ≤ λb are supposed to represent “complicating” constraints. The sense in which Q is “easy” is that the al m gorithm assumes that there is a fast subroutine that, given a positive row vector y ∈ , ∗ computes z = argmin{cz : z ∈ Q}, where c = yA. Before explaining the ideas underlying this algorithm, we will first show how to cast the maximum multicommodity flow problem in this setting. We will perform a bisection search for the maximum value f such that there is feasible flow of total value f . We will work from the exponential linear programming formulation (5.6)-(5.8). The objective function (5.6) has been transformed into a constraint that the total flow value is exactly equal to f . The polytope Q is the set of of solutions satisfying this total flow constraint as well as the non-negativity constraints (5.8); note that this is just a rescaled simplex. The constraints Az ≤ λb correspond to the capacity constraints (5.7), where λ reflects the amount by which the capacities need to be multiplied so as to ensure that z is a feasible flow. Thus, for a candidate flow value f , we must decide if the optimum λ ∗ is at most 1. If we can approximate λ within a factor of (1 + ), then we can also approximate the optimal flow value within a factor of (1 + ). Finally, we need to provide the subroutine to optimize over Q. There always exists an optimal solution at one of its extreme points; each extreme point of Q has exactly one coordinate set equal to f , and the rest set equal to 0. Hence, an optimal solution can be found by determining the smallest objective coefficient and setting the corresponding coordinate to f . In this setting, each coordinate of y corresponds the capacity constraint of one edge e ∈ E. The vector yA specifies the objective function coefficients, and the coordinate of yA corresponding to the flow variable f (P) has value equal e∈Py(e). Hence, we wish to find the coordinate, or equivalently the path between some (si ,ti ) pair, for which the total edge length (with respect to the lengths y) is smallest. This can be done, for example, by Dijkstra’s algorithm, starting at each source node si , i = 1,...,k, and then choosing the minimum-length path found over all k computations. Hence, the maximum multicommodity flow problem can be cast into the framework of [PST95]. The main idea of the algorithm of [PST95] is as follows: iteratively maintain a solution z (or in our case, a flow of value f ). This solution is feasible for some choice of λ, and we wish to change z so that the corresponding minimal choice of λ decreases over the execution of the algorithm. In our application, λ can be viewed as the minimum value so that the current flow is feasible with respect to the adjusted capacities λc(e). For the current solution (z,λ), we wish to focus on the constraints Az ≤ λb that are most important in determining λ; in the flow setting, these correspond to the edges e that are saturated, or nearly saturated, to their adjusted capacity. For each of these constraints, we wish to perturb the current z so as reduce the value of the left-hand side; in our example, the total flow on each nearly saturated edge should be reduced. In our particular case, one way to do this would be to find a si − ti path for which none of the edges is nearly saturated, increase the flow on that path, and decrease the flow on all other paths (uniformly) so that once again the total flow value is f . Instead, the algorithm selects a path as follows: for each edge e,weset y(e) = (1/c(e))·exp(α f (e)/c(e)), where f (e) denotes the total flow on e in the current solution and α is a parameter that is proportional to 1/λ; then compute a shortest si − ti path with respect to these lengths y(e). Observe that this approach can be viewed as a continuous version of the path selection rule described above: short edge lengths correspond to undersaturated edges. In general, we compute yi = (1/bi ) · exp(αai z/bi ), where ai is the ith row of A, compute ∗∗ z = argmin{yAz : z ∈ Q}, and set z = (1 −σ)z +σz , where 0 <σ < 1 is a parameter set by the algorithm. The analysis of the running time of the algorithm is based on showing that each iteration decreases the exponential potential function = i exp(αai z/bi ). The overall running time depends on the width ρ of the formulation, which is the minimum λ such that every z ∈ Q is feasible: ρ = maxz∈Q maxi aiz/bi . Plotkin, Shmoys, & Tardos show that O(ρ −2 log(m −1)) iterations suffice to find a solution within a factor of (1 + ) of optimal, where m denotes the number of rows in A. The width of the formulation proposed above for the maximum multicommodity 5.2 MINIMUM MULTICUTS AND MAXIMUM MULTICOMMODITY FLOW 11 procedure Pipe-Cut(G,x) f we shall assume that x(e) is given as a fraction with denominator at most g ¯ V ←V (G); l ←0; ←1/(22); repeat fix i such that {si ,ti }⊆V¯; r ∗= argmin{Cx (si ,r)/Vx (si ,r): r =distx (si ,v)− ,v ∈V¯};l ←l +1; Vl ← Bx (si ,r ∗ ); V ← V¯−Vl ; ¯ until |{si ,ti }∩V¯|≤1, for each i =1,...,k; output (V1,V2,...,Vl ,V ). ¯ FIGURE 5.2 The algorithm Pipe-Cut flow is at most maxef/c(e); if there are small capacity edges, then this quantity can be quite large. However, if we delete all edges of capacity at most f/m, then the resulting width is at most m/ . Furthermore, by modifying the instance in this way we can change the optimum by at most a further (1+ )factor. The subroutine required for each iteration is nothing more than k shortest path computations, and so if we ignore log factors and set to a constant, we get an overall running time of O˜(km2). Significantly, by rescaling y, we can also show that the algorithm produces a near-optimal solution x for the linear program (5.3), (5.4), and (5.9), or in other words, a near-optimal fractional multi- cut. Finally, we should note that there exist more sophisticated approaches to formulate the maximum multicommodity flow problem as fractional packing problem, which lead to improved running times, but we shall instead discuss these ideas in the context of the maximum concurrent flow in Section 5.3. 5.2.4 FINDING A GOOD MULTICUT Garg, Vazirani, & Yannakakis [GVY93] gave an algorithm that takes as input a pipe system of volume φ, and computes a multicut of cost O(logk)φ. If we start with the optimal pipe system of volume φ ∗, since φ ∗ is a lower bound on the minimum-cost multicut, the resulting algorithm is an O(logk)-approximation algorithm. Next we describe the algorithm Pipe-Cut of Garg, Vazirani, & Yannakakis, which is summarized in Figure 5.2. The algorithm iteratively produces the desired multicut. At the start of iteration l, the Pipe-Cut has already produced a sequence of disjoint sets of vertices V1,...,Vl−1, with the property that, for each j =1,...,l −1, the set Vj contains at most one of si and ti , for each i =1,...,k; furthermore, for each set Vj we have specified one commodity i(j), such that the set Vj contains exactly one of the terminals si(j) and ti(j). Let V = ¯ V −(V1 ∪···∪Vl−1), and consider the graph induced by V and its corresponding pipe ¯ ¯ have found a multicut: {e ∈ E : e =(u,v), u ∈Vj ,v∈Vj , j = j }, where Vl =V¯, and this is the desired output. Otherwise, select any commodity i such that both si and ti are in V . In this iteration will find a particular subset Vl ⊂V¯ such that exactly one of si and system. If there does not exist a commodity i such that both si and ti are in V , then we ¯ 9 2 8 1 3 7 4 6 5 3 3 4 5 4 3 2 6 3 B(1,5) ={1,2,3,4} FIGURE 5.3 A pipe system & a ball of radius 5 centered at vertex 1 ti are in Vl , and hence we can set i(l) =i. Before describing the details of the remainder of this iteration, we first introduce some notation. Let Bx (si ,r) denote the set of vertices that are contained within a ball of radius r centered at vertex si in the pipe system, where the distances are given with respect to the length function x. Figure 5.3 gives an example of a portion of a pipe system and ball centered at one of its vertices. More formally, let distx (u,v) denote length of the shortest path between vertices u and v with respect to the length function x, and, for each v ∈V , set Bx (v,r) ={u ∈V : distx (u,v) ≤r}. (5.10) We shall define the part of the pipe system that is within radius r of si in the following way: first, we include each pipe that corresponds to an edge with both of its endpoints in Bx (si ,r); second, for each edge with exactly one endpoint in Bx (si ,r), we include the fraction of the corresponding pipe that is still within a distance r of si ; finally, we will add a “point volume” at si of volume φ/k. More formally, the volume of the pipe system within radius r of vertex si is defined to be Vx (si ,r) =φ/k + c(u,v)x(u,v)+ c(u,v)(r −distx (v,u)), u,v∈Bx (v,r)(u,v)∈δ(¯ Bx (si ,r)) (5.11) where δ¯={(u,v) ∈E : u ∈Bx (si ,r) and v ∈V¯−Bx (si ,r)}. 5.2 MINIMUM MULTICUTS AND MAXIMUM MULTICOMMODITY FLOW 13 We shall set Vl = Bx(si,r) for a judicious choice of radius r. Let the cost Cx(si ,r) = c(u,v). (5.12) (u,v)∈δ(¯ Bx (si ,r)) We shall choose the radius r to be a value less than 1/2 such that Cx(si ,r)/Vx(si ,r) is sufficiently small. More precisely, to guarantee the claimed performance, we need only choose a radius r = ρl for which this ratio is at most 2ln2k; in fact, it is possible to choose the radius essentially minimizing this ratio, and the minimum will be guaranteed to be this small. We shall see that it is easy to find a good choice for ρl, but first we will prove a few useful facts about the function Vx(si ,r) (as a function of r). If there does not exist a vertex v such that distx(si ,v) = r, then this function is differentiable at r, and its derivative is equal to the total cost of the cut defined by the current radius r, Cx(si ,r). The function might not even be continuous at these breakpoints corresponding to vertices in V, but it ¯ is an increasing function of r nonetheless. Furthermore, the cost Cx(si ,r) changes only at these breakpoints. Hence, if we want to minimize the cost per volume ratio, this minimum is achieved as the radius approaches one of these breakpoints. Since the algorithm depends on the radius only in selecting Vl = Bx(si,ρl ), we need only set ρl to a value sufficiently close to the limiting point. There are two main points in analyzing the performance of the algorithm Pipe-Cut. The first step is to show that the algorithm does produce a feasible multicut. This is quite simple, since we must only prove that the set Vl contains at most one terminal for each commodity. To prove this, we observe that the feasibility of the length function implies that, for each commodity i, its two terminals si and ti are at least distance 1 apart from each other. However, we set Vl to be a ball of radius less than 1/2, and any two points within it must be of distance less than 1 apart. The second main point is to show that Cx(si ,ρl)/Vx(si,ρl ) ≤ 2ln2k, and then show that this implies the claimed performance for the algorithm. For notational simplicity, let f (r) = Vx(si ,r). Recall that ∂Vx(si ,r) df Cx(si ,r) == , ∂r dr whenever the derivative is well-defined. Suppose that for each radius r within the interval (0,1/2), the ratio Cx(si ,r)/Vx(si ,r)> 2ln2k. If we consider any interval (r1,r2) throughout which f (r) is differentiable, we have that f (r)/f (r)> 2ln2k, or equivalently, that d (ln f (r)) > 2ln2k. dr If we integrate both sides, we see that this implies that ln f (r2) − ln f (r1)>(r2 −r1)(2ln2k). (5.13) If f were differentiable throughout the interval (0,1/2), (5.13) would imply that ln( f (1/2)/f (0)) > ln2k; that is, f (1/2)> 2kf (0) = 2φ. But this is impossible, since the total volume in the pipe system, including the additional point volume, is at most (1 +1/k)φ, and hence f (1/2) cannot exceed this value. Of course, f might not be differentiable throughout the inter val (0,1/2). We can apply the same trick to each interval throughout which f is differentiable. By combining the results of these integrals, along with the fact that f does not decrease at any of the breakpoints, we can still conclude that ln f (1/2)−ln f (0)>ln2k, which is not possible. Hence, we have shown the following lemma. LEMMA 5.2 There exists a radius r <1/2, such that Cx (si ,r)/Vx (si ,r)≤ 2ln2k. Finally, we must bound the total cost of the multicut found by the algorithm Pipe- Cut. Consider some edge (u,v) for which u ∈ Vj , v ∈ Vj , j ≤ j . The cost of this edge, c(u,v), is included in the sum Cx (si(j),ρj ). Thus, we can upper bound the cost of the multicut found by the algorithm by j Cx (si(j),ρj ). By Lemma 5.2, for each iteration j we have that Cx (si(j),ρj )≤ 2ln(2k)Vx (si(j),ρj ). If we consider the balls Bx (si(j),ρj ) found in each iteration, they each have an associated volume that corresponds to disjoint portions of the original pipe system. The total volume in the original pipe system is at most 2φ: there were φ units of volume originally, and at most k point volumes, each of volume φ/k, that are added throughout the course of the algorithm. Hence, the cost of the multicut is no more than 2ln(2k)Vx (si(j),ρj )≤ 4ln(2k)φ, j and we have obtained the result of Garg, Vazirani, & Yannakakis [GVY93]. THEOREM 5.1 The algorithm Pipe-Cut, when applied to an optimal fractional mul ∗ ticut x , isa4ln(2k)-approximation algorithm for the minimum multicut problem. Since we have shown that there always exists a multicut of cost at most 4ln(2k) times the cost of the optimal fraction multicut, we have also proved the following approximate max-flow min-cut theorem for multicommodity flow. COROLLARY 5.1 For any instance with k terminal pairs, the cost of the minimum multicut is always at least the maximum multicommodity flow value, and is always at most O(logk) times as much. SPARSEST CUTS AND MAXIMUM CONCURRENT FLOW 5.3 In this section we will present approximation algorithms for the sparsest cut problem for undirected graphs; these algorithms will also play a central role in the design of approximation algorithms for the balanced cut problem. 5.3 SPARSEST CUTS AND MAXIMUM CONCURRENT FLOW 15 S1 3 5 terminals of commodity 1 with d(1) =5 terminals of commodity 2 with d(2) =3 6 3 2 4 5 2 3 3 S2 capacity of cut S1 =15 ⇒ρ(S1)=3 demand separated by S1 =5 capacity of cut S2 =12 ⇒ρ(S2)=1.5 demand separated by S2 =8 FIGURE 5.4 Illustrating the sparsity ratio of a cut 5.3.1 THE SPARSEST CUT PROBLEM In the sparsest cut problem, we are given an undirected graph G =(V,E), where there is a positive cost c(e) associated with each edge e ∈ E, and k pairs of vertices (si ,ti ), i =1,...,k, where there is a positive demand d(i) for the commodity corresponding to (si ,ti ). For each subset of nodes S ⊆V , let I (S) indicate those terminal pairs that are disconnected by deleting the edges in δ(S)={(u,v)∈E : u ∈S,v ∈S}; more formally, I (S)={i : |S ∩{si ,ti }|=1}. The sparsity ratio of the set S, ρ(S), is the ratio of the total cost of the edges connecting S with V −S to the total demand separated by this cut: c(e) e∈δ(S) ρ(S) = . d(i) i∈I (S) We wish to find the set S for which ρ(S) is minimum. Observe that the definition of the sparsity ratio of a cut captures the fact that in some settings we might be most interested in “getting our money’s worth” in that we are willing to pay more for a cut if it succeeds in disconnecting a greater amount of the demand. Figure 5.4 illustrates these notions for a particular instance. Although we have defined the sparsity ratio of a cut in terms of a subset of vertices, we can instead view a cut as a subset of edges whose deletion disconnects the graph. We can extend the notion of sparsity ratio to apply to a subset of edges F whose deletion leaves a graph with more than two connected components. Let S ={S1,S2,...,Sc}be a partition of V such that each Sj denotes the vertex set of a connected component in ¯ G =(V,E −F). Let I (S) denote the set of terminal pairs that are disconnected by S: {i : si ∈Sj , ti ∈Sk , j =k}. The sparsity ratio of S is then e∈Fc(e) ρ(S)= . d(i) i∈I (S) The following proposition merely asserts that an average cannot be less than the minimum of its components. PROPOSITION 5.1 For any non-negative integers, a1,...,an , and positive integers, nn b1,...,bn , mini=1,...,n ai /bi ≤( 1 ai )/( i=1 bi ). i= Applying this to our setting, we obtain the following lemma. LEMMA 5.3 Let S ={S1,S2,...,Sc }be a partition of V such that each Sj , j =1,...,c, denotes the vertex set of a connected component in G =(V,E −F). Then ¯ min j=1,...,cρ(Sj )≤ρ(S). This lemma implies that we can find a good set of edges to delete without concern for the number of connected components in the remaining graph (provided that it is at least two). Furthermore, it implies that we can obtain a simple (non-linear) integer programming formulation of the sparsest cut problem. We let x(e), e ∈E be a 0-1 variable that indicates whether edge e is cut, and let y(i), i =1,...,k, be a 0-1 variable that indicates whether commodity i is disconnected by this cut. As in the previous section, let Pi denote the set of paths between si and ti , i =1,...,k. e∈Ec(e)x(e) minimize k 1 d(i)y(i)i= (5.14) subject to x(e)≥y(i), for each P ∈Pi , i =1,...,k, (5.15) e∈P y(i) ∈{0,1}, x(e) ∈{0,1}, for each i =1,...,k, for each e ∈E. (5.16) (5.17) Consider the relaxation of this formulation in which constraints (5.16) and (5.17) are replaced by y(i)≥0, i =1,...,k, and x(e)≥0, e ∈E, respectively. First, observe that if (x,y) is a feasible fractional solution, then for any constant α> 0, the solution (αx,αy)is also feasible, and the two solutions have equal objective function value. Consequently, it is without loss of generality that we have not constrained each variable to be at most 1. Furthermore, we can choose a normalization of the variables by requiring k that 1 d(i)y(i) =1, and by doing this, we have obtained the following linear pro- i= gramming relaxation of the sparsest cut problem: minimize c(e)x(e) (5.18) e∈E 5.3 SPARSEST CUTS AND MAXIMUM CONCURRENT FLOW 17 subject to k d(i)y(i)=1, i=1 (5.19) x(e)≥ y(i), e∈P y(i)≥0, for each P ∈Pi , i =1,...,k, for each i =1,...,k, (5.20) (5.21) x(e)≥0, for each e ∈ E. (5.22) This linear program can be solved in polynomial time; we defer further discussion of this until Section 5.3.5 Rao [Rao87] focused attention on the sparsest cut problem, and showed its importance in computing a balanced cut (albeit only in the context of planar graphs). Leighton & Rao [LR88] considered arbitrary graphs, but restricted attention to the case in which there is a commodity for each pair of vertices, and each demand d(i)=1. For this case, they showed how to construct a cut of sparsity ratio within a O(logn) factor of the optimal value of the linear relaxation. Klein, Rao, Agrawal & Ravi [KRAR95] considered the general case, and gave an O(logC log D)-approximation algorithm, where C denotes the sum of the edge costs in the graph and D denotes the total demand; Tragoudas [Tra91] subsequently improved this performance guarantee to O(logn log D). Kahale [Kah93] showed how to obtain a bound of O(logk log D) by showing, in effect, how to reduce the sparsest cut problem to the minimum multicut problem. Plotkin & Tardos [PT95] gave a sophisticated rounding technique that yields an improved performance guarantee of O(log2 k). Finally, work of London, Linial, & Rabinovich [LLR95] and Aumann & Rabani[AR95] led to a much simpler O(logk)-approximation algorithm for the general case, thereby matching the performance of Leighton & Rao for the all-pairs unit-demand problem. 5.3.2 REDUCING THE SPARSEST CUT PROBLEM TO THE MINIMUM MULTICUT PROBLEM We will show how to use the information given by an optimal fractional solution to (5.18) (5.22) to construct a sparse cut. We shall actually give two algorithms to do this. In this subsection, we will present the result of Kahale [Kah93], which relies on Theorem 5.1 to produce a cut of sparsity ratio within a factor of O(log D logk)of the fractional opti k mum, where D denotes the total demand 1 d(i). i= The main idea of this algorithm is quite simple. We use the optimal fractional solution (x,y)to identify a particular subset S of the commodities and apply the approximation algorithm of Section 5.2 to find a multicut that separates each commodity in S. The choice of S will ensure that the multicut found is sparse, and hence, by Lemma 5.3, we find a sparse cut. Let D = i∈Sd(i)and ymin =mini∈Sy(i). We will choose S such that ¯ 1 ymin ≥ , (5.23) D¯·H(D¯) where H(k)=1 +1/2 +1/3 +···+1/k is the kth Harmonic number; it is straightfor ward to show that H(k) ≤log k +1. Suppose that we apply the multicut approximation e algorithm given in Section 5.2 to the modified instance in which S specifies the terminal pairs that must be separated (and there are no specified demands). Given any feasible fractional solution (x, y) for the sparsest cut relaxation, (5.18)-(5.22), we can construct a solution x¯(e) =x(e)/ymin, for each e ∈ E. We shall argue that x¯ is a feasible fractional multicut for the modified instance. To see this, observe that the constraints (5.20) imply that ¯x(e) ≥1, for each P ∈Pi , i ∈ S. e∈P By (5.23), c(e) ¯x(e) ≤ ¯De ·H( ¯D)·( c(e)x(e)); since ¯x is a feasible fractional mule ticut, the cost of the optimal fractional multicut is clearly at most this much. The multicut approximation algorithm of Garg, Vazirani, & Yannakakis produces a multicut S of cost within an O(log|S|) factor of the optimal fractional solution, and hence the cost of S is O(logk ·D¯·H(D¯)·( c(e)x(e))). Since S is a multicut that disconnects each terminal e ¯ pair in S, d(i) ≥ i∈Sd(i) = D; hence ρ(S) is O(logk ·H(D¯))· c(e)x(e). i∈I (S) e Since (x, y) is an optimal solution to the linear relaxation (5.18)-(5.22), we see that ρ(S) is within O(logk ·H(D¯)) factor of optimal. We must still show how to construct the required set S that satisfies (5.23). Assume, without loss of generality, that the commodities are indexed such that y(1) ≥ y(2) ≥ ···≥ y(k). Let D( j) = j 1 d(i). We shall show that there exists j∗ such that y( j∗ ) ≥ i= 1/(D( j∗ ) ·H(D)) and hence S ={1,2,..., j ∗} satisfies (5.23). Suppose, for a contradiction, that 1 y(i)< , for each i =1,...,k. D(i)H(D) This would imply that k kd(i) d(i)y(i)< H(D) ·D(i) i=1 i=1 1 kD(i) −D(i −1) = H(D) i=1 D(i) kD(i) 11 ≤ H(D) s i=1 s=D(i−1)+1 =1, which contradicts (5.19). 5.3.3 EMBEDDINGS AND THE SPARSEST CUT PROBLEM In this section, we give an improved rounding method due to Linial, London, & Rabinovich [LLR95] and Aumann & Rabani [AR95]; this yields an O(logk)-approximation algorithm for the sparsest cut problem. In Section 5.2, we viewed the fractional multicut x as specifying a length function on the edges. We can similarly interpret the variables x in the linear programming relaxation of the sparsest cut problem; the variable y(i) cor 5.3 SPARSEST CUTS AND MAXIMUM CONCURRENT FLOW 19 respondingly represents the distance between si and ti , i =1,...,k. Suppose that this length function were derived from an embedding of the input graph G =(V,E)in some low-dimensional space with L1 norm: that is, there is a function f : V → d such that x(e)= f (u)− f (v) 1, for each edge e =(u,v) ∈ E, and y(i)= f (si )− f (ti ) 1 for each i =1,...,k. We first shall show if such an embedding were achievable, then we could find a cut of sparsity ratio at most c(e)x(e); that is, if the optimal fractional e solution (x,y) has the property that it can be derived from such an embedding, then, given the embedding, we can find an optimal sparsest cut. It is, of course, too much to hope for that the optimal length function admits such an embedding. The crux of the approximation algorithm for the sparsest cut problem is an algorithm to find an embedding that roughly corresponds to the distances. The embedding algorithm that we shall give is due to Linial, London, & Rabinovich [LLR95], which is based on a result of Bourgain [Bou85], which gives an exponential algorithm to find an embedding. The application of this embedding algorithm to the sparsest cut problem was discovered by Aumann & Rabani [AR95], based on a preliminary version of [LLR95], and an essentially identical result was independently discovered by Linial, London, & Rabinovich [LLR95], and published together with their embedding algorithm. LEMMA 5.4 Let (x,y) be a feasible solution to the linear program (5.18)-(5.22) of objective function value αsuch that there exists a function f : V → d with the property that x(e)= f (u)− f (v) 1, for each e =(u,v)∈E, (5.24) and y(i)= f (si )− f (ti ) 1, for each i =1,...,k. (5.25) Then, given f , one can find a cut S of sparsity ratio ρ(S)at most α in polynomial time. Proof. We first try to understand some simple consequences of the existence of the embedding f . This embedding defines a metric μ on the set of vertices V : that is, for each pair of vertices u,v ∈ V , we have a value μ(u,v) = f (u)− f (v) 1, and these values satisfy the triangle inequality: for each u,v,w∈V , μ(u,v)+μ(v,w)≥μ(u,w). (If e =(u,v) ∈ E, then we shall also use μ(e) to denote μ(u,v).) We can also derive a metric corresponding to each subset S ⊆V : let μS(u,v) be 1 if |{u,v}∪S|=1, and 0 otherwise. To see that this defines a metric, observe that for any u,v,w ∈V ,if (u,w) crosses the cut defined by S, then exactly one of (u,v)and (v,w)must cross this cut too. The crucial property of μthat we shall use is that it is in the cone defined by the cut metrics μS: that is, there exists λS ≥0 such that μ(u,v)= λS ·μS (u,v), for each u,v ∈V. (5.26) S⊆V To show this, we start by considering just the contribution of the first coordinate of our d-dimensional space to μ, |f1(u)− f1(v)|. Suppose that the vertices of V are indexed v1,...,vn such that f1(v1) ≤ f1(v2) ≤···≤ f1(vn ). Then, for each pair of vertices v j ,vj , j > j , we can rewrite the contribution of the first coordinate to μ(vj ,vj ) as j−1 f1(vj ) − f1(vj ) = f1(v +1) − f1(v ). =j Let S( ) ={v1,...,v }, =1,...,n. Note that the term f1(v +1)− f1(v ) is included in this sum precisely when the distance, with respect to the metric μS( ), between vj and vj is 1. In other words, n f1(vj ) − f1(vj ) = ( f1(v +1) − f1(v )) ·μS( )(vj ,vj ). =1 Observe that if j < j , then the right-hand side of this equation still gives |f1(vj ) − f1(vj )|. Hence, we have shown that the contribution of the first coordinate to μ can be expressed in the claimed form. By repeating this construction for each coordinate and adding them together, we have produced a decomposition of μ satisfying (5.26). Note that although there are 2n sets S ⊆V , we have produced a decomposition that uses at most nd sets. Second, we have given an efficient algorithm to produce this decomposition. Finally, it is not hard to show that (5.26) precisely characterizes those metrics that correspond to an embedding in L1; they are precisely those metrics that lie in the cone defined by the cut metrics, or more simply the cut cone. For much more information the cut cone, and its relationship to embeddings and multicommodity flows, the reader is referred to the expository paper of Avis and Deza [AvisD91]. However, we shall now see that (5.26) easily implies the lemma. Let μ = S∈S λS μS, as in (5.26), where λS > 0 for each S ∈S. But then, by substituting μ(e) for x(e), μ(si ,ti ) for y(i), and recalling that (x, y) is feasible, we see that λS ·μS(e)λSe∈Ec(e)μS(e) e∈Ec(e) S∈S S∈S α = c(e)x(e) = k = k . e∈E 1 d(i)λS ·μS(si ,ti )λS 1 d(i)μS(si ,ti ) i= S∈S S∈S i= Using the fact that μ(S)(u,v) =1 exactly when (u,v) crosses the cut defined by S,we see that λSc(e) c(e) S∈S e∈δ(S) e∈δ(S) α =≥minS∈S =minS∈S ρ(S), d(i) S∈S λSi∈I (S) d(i) i∈I (S) where the inequality follows from Proposition 5.1. Hence, we have shown that one of the cuts S ∈S has sparsity ratio at most α. The algorithm Embed-Cut, given in Figure 5.5, summarizes this quite trivial procedure to find a good cut, given an embedding. Finally, it is not hard show that if there are only two commodities, then there exists an ∗ optimal length function (x , y ∗ ) for which a suitable embedding f is easy to construct; by applying Lemma 5.4, one obtains the min-max theorem of Hu [Hu63]. 5.3 SPARSEST CUTS AND MAXIMUM CONCURRENT FLOW 21 5.3.4 FINDING A GOOD EMBEDDING We can view equations (5.24) and (5.25) as taking an embedding f , and from the embedding constructing a fractional solution (x,y). This solution is not necessarily feasible, since although (x,y)satisfies constraints (5.20), it need not satisfy (5.19). However, this is not significant, since this is just a question of normalization: if id(i)y(i)=β, then (x/β,y/β)is a feasible fractional solution; we shall refer to this solution as the one induced by the embedding f . The O(logk)-approximation algorithm for the sparsest cut problem is an immediate corollary of the following result: given any feasible solution (x,y) to (5.19)-(5.22), we can construct an embedding f which induces a feasible fractional solution (x¯,y¯) such that e∈Ec(e)x¯(e) is O(logk) e∈Ec(e)x(e). The embedding is constructed by a randomized algorithm: that is, for any input, the solution induced by the embedding is sufficiently good with high probability, where the probability depends only on the random choices made by the algorithm, and not on any (probabilistic) assumption about the input. Randomized approximation algorithms are discussed in much greater detail in Chapter 11 of this volume, and we shall rely on basic tools of analysis that are developed in that chapter. Alternatively, the reader can consult the recent book of Motwani & Raghavan [MR95] for an even more thorough investigation of this area. Let T denote the set of terminal vertices {si ,ti : i =1,...,k}; for simplicity of notation, we shall assume that |T |is a power of 2, i.e., |T |=2τ . We shall use the notation distx (u,v)to denote the length of the shortest path between vertices u and vwith respect to the length function x. Furthermore, for any set of vertices A ⊆V , let distx (u,A) = minv∈A distx (u,v). Given a feasible fractional solution (x,y), our embedding will be quite easy to compute. We shall let L =q logk where q is a constant that will be determined later. The dimension of the embedding is d =τL =O(log2 k). For =1,...,L, t =1,...,τ, construct the set At by choosing 2τ−t =k/2t points from T uniformly at random with replacement (that is, a given element of T may be selected more than once). The embedding function f is then defined to be ft (v)=distx (v,At ), for each v ∈V. (5.27) We first state the two key lemmas, show how they imply that the embedding is good, and then give their proofs. LEMMA 5.5 For each edge e =(u,v), f (u)− f (v) 1 ≤d ·x(e). procedure Embed-Cut(G, f ) f Each vertex v ∈V (G) is embedded at (f1(v),..., fd (v))g (j∗ ,ξ ∗ )← argmin{ρ(S(j,ξ)): ξ = fj (v),v ∈V (G), j =1,...,d}; output S(j∗ ,ξ ∗ )={v : fj∗(v)≤ξ ∗}. FIGURE 5.5 The algorithm Embed-Cut LEMMA 5.6 With probability at least 1/2, f (si ) − f (ti ) 1 ≥ L · y(i)/88, for each i = 1,...,k. (5.28) Since it is easy to check if a particular embedding f satisfies (5.28), we can arbitrarily increase the probability of success by repeatedly constructing independent embeddings. Furthermore, by iterating until an embedding satisfying (5.28) is found, we can obtain a Las Vegas-style algorithm, where the performance is guaranteed, and the expected running time is polynomial. We can combine Lemmas 5.5 and 5.6 in the obvious way. We focus on the case in which f satisfies the property (5.28). In this case, kk d(i) f (si ) − f (ti ) 1 = (logkd(i)y(i)) = (logk). (5.29) i=1 i=1 On the other hand, Lemma 5.5 implies that c(e) f (u) − f (v) 1 = O(log2 k) c(e)x(e). (5.30) (u,v)=e∈Ee∈E Combining these two equations, we get the following theorem. THEOREM 5.2 With probability at least 1/2, the embedding f induces a feasible fractional solution (x¯, y¯) of objective function value c(e)x¯(e) = O(logk) c(e)x(e). e∈Ee∈E By applying this theorem starting with a optimal solution (x, y) to the linear program (5.18)-(5.22), we obtain the following corollary. COROLLARY 5.2 There is a randomized polynomial-time algorithm that, with probability at least 1/2, computes a cut of sparsity ratio within an O(logk) factor of optimal. As we observed above, it is possible to verify efficiently if the embedding found is sufficiently good, and hence we can obtain an improved algorithm for which the performance guarantee holds with high probability; furthermore, by running the embedding algorithm until a good one is found, we obtain a randomized algorithm that runs in polynomial expected time, and is guaranteed to produce a cut of sparsity ratio within an O(logk) factor of optimal. Linial, London, & Rabinovich and, independently, Garg [Gar95] have subsequently shown that, like many other randomized algorithms whose analysis is based on Chernofftype calculations, this algorithm can be derandomized. However, this deterministic version does not simply follow from an application of standard derandomization techniques to this algorithm; we shall omit the details. THEOREM 5.3 There is a deterministic polynomial-time O(logk)-approximation algorithm for the sparsest cut problem. We now return to the proofs of Lemmas 5.5 and 5.6. 5.3 SPARSEST CUTS AND MAXIMUM CONCURRENT FLOW 23 Proof of Lemma 5.5. This is quite straightforward to show. For any set A ⊆V and edge (u,v) =e ∈E, distx (u, A) ≤x(e) +distx (v, A). Equivalently, we have that distx (u, A) −distx (v, A) ≤x(e). By the same argument, we see that distx (v, A) −distx (u, A) ≤x(e). By definition, f (u) −f (v) 1 =|ft (u) −ft (v)|= |distx (u, At ) −distx (v, At )|. t, t, Combining this with the inequalities above, we see that f (u) −f (v) 1 ≤τ Lx(e) =d ·x(e). Proof of Lemma 5.6. This is the crucial observation that drives the embedding-based proof of Bourgain [Bou85] and Linial, London, & Rabinovich [LLR95], and its proof is rather involved. We first focus on one particular commodity i, and prove that with probability at least 1 −(1/2k), f (si )−f (ti ) 1 = (L ·y(i)). Before proving this, observe that this claim implies the lemma: the probability that property (5.28) fails to hold is at most k times the probability that it fails for one particular commodity. For v ∈{si ,ti }, let Bx (v,r) ={w ∈T : distx (v,w) ≤r}, and let B◦(v,r) ={w ∈T : distx (v,w) < r}. x Let r0 =0, and let rt be the smallest value of r such that |Bx (v,r)|≥2t , for both v ∈ {si ,ti }. Furthermore, we let tˆdenote the smallest value of t for which rtˆ≥y(i)/4, and reset rtˆ=y(i)/4. Observe that since y(i) ≤distx (si ,ti ) (by constraints (5.20)), we have ensured that B(si ,rtˆ) and B(ti ,rtˆ) are disjoint. To give some intuition of the proof, we wish to show that f embeds si and ti so that they are reasonably far apart as compared to y(i). Since we are computing distances in the L1 norm, we can prove this by showing that, with sufficiently high probability, each coordinate of f contributes a certain distance to the total distance between si and ti . More precisely, we will show that each of the coordinates ft is likely to contribute a distance rt −rt−1. By summing this over the L choices for , we get that those coordinates are likely to contribute (L(rt −rt−1)). By summing this bound for t =1,...,tˆ, we get that this sum is (Lrtˆ) = (Ly(i)), which is what we wish to prove. Observe that A ∩B◦(si ,rt ) =∅if and only if distx (si , A) ≥rt ; alternatively, we have x that A ∩Bx (ti ,rt−1) =∅if and only if distx (ti , A) ≤rt−1. Thus, if we let Et , t =1,...,tˆ, =1,...,L, denote the event that At ∩B◦(si ,rt )=∅ and At ∩Bx (ti ,rt−1)=∅, x then Et implies that |ft (si )−ft (ti )|=|distx (si ,At )−distx (ti ,At )|≥rt −rt−1. Hence, we are interested in showing that Et is likely to occur. In order to bound this probability, we shall first do some preliminary calculations. Suppose that we are given a ground set X in which there is a specified good subset G and disjoint bad subset B; finally, A is formed by selecting p elements of X independently and uniformly at random from X (with replacement). Then Pr[A ∩G =∅and A ∩B =∅] =Pr[A ∩G =∅|A ∩B =∅] ·Pr[A ∩B =∅] ≥Pr[A ∩G =∅] ·Pr[A ∩B =∅], where the last inequality follows from the observation that knowing that the elements of A are not selected from B can only increase the likelihood that they are selected from G. For any subset Y ⊆X, the probability that A ∩Y =∅is (1 −| |YX| | )p.If p =|X|/|Y |, then this bound approaches 1/e as p tends to infinity, and is always within the interval [1/4,1/e] (provided |X|/|Y |> 1). More generally, if p =β(|X|/|Y |), then the probability that A ∩Y =∅is within the interval [(1/4)β,(1/e)β]. Now consider the event Et , t =1,...,tˆ, =1,...,L. We can assume without loss of generality that it was the ball around si that determined the radius rt (since otherwise we could interchange si and ti ). We can apply the previous probability calculations by setting A = At , X =T , B = B◦(si ,rt ) and G = Bx (ti ,rt−1). We have that x p =2τ−t , |X|=2τ , |B|<2t and |G|≥2t−1; hence, p <|X|/|B|and p ≥(1/2)|X|/|G|. This implies that Pr[A ∩B =∅] ≥1/4 and Pr[A ∩G =∅] ≥(1 −(1/e)1/2). Hence, Pr[Et ] ≥(1−(1/e)1/2)/4 ≥1/11, t =1,...,tˆ, =1,...,L. (It is important to note that the above calculation applies verbatim to the seemingly exceptional case when t =tˆ.) If we fix a particular t =1,...,tˆ, and define X , =1,...,L, to be the 0-1 variable that indicates whether (or not) event Et occurs, then we can apply the Chernoff bound L to show that 1 X does not deviate too much from its expectation, which is at least = L/11. We shall apply this bound in a very crude way, and will pay no attention to optimizing the constants involved. In particular, we shall use the following statement of the Chernoff bound: if E[ X ] =μ, then Pr[ X <μ/2] ≤exp(−μ/8). (This follows, for example, from Theorem 4.2 of [MR95].) Since μ≥L/11 =q logk/11, we see that if we set q to be, say, 200, then this probability is less than 1 . Most (2k)log(2k) importantly, if X ≥L/22, then we know that for L/22 of the components ft , = 1,...,L, the event Et occurs, and so L |ft (si )−ft (ti )|≥(rt −rt−1)L/22. (5.31) =1 We have shown that for any fixed value of t =1,...,tˆ, (5.31) fails to hold with probability at most 1/(2k log(2k)). Since tˆ≤log(2k), it follows that (5.31) holds for every t =1,...,tˆ, with probability at least 1 −(1/2k). But this implies that, with probability 5.3 SPARSEST CUTS AND MAXIMUM CONCURRENT FLOW 25 at least 1 −(1/2k), tˆ Ltˆ |ft (si )−ft (ti )|≥ (rt −rt−1)L/22 =rtˆL/22 =y(i)L/88. (5.32) t=1 =1 t=1 This completes the proof of Lemma 5.6. 5.3.5 THE MAXIMUM CONCURRENT FLOW PROBLEM We have just seen that one can compute a cut S of sparsity ratio ρ(S) within a factor of O(logk) of the optimal fractional solution to (5.18)-(5.22). By considering the linear programming dual to this, we can obtain an elegant approximate max-flow-min-cut theorem for multicommodity flow. The dual of (5.18)-(5.22) is as follows: maximize α (5.33) subject to k f (P)≥αd(i), P∈Pi f (P)≤c(e), for each i =1,...,k, for each e ∈E, (5.34) (5.35) i=1 P∈Pi (e) f (P)≥0, for each P ∈Pi ,i =1,...,k. (5.36) This problem is called the maximum concurrent flow; it is the version of the multicommodity flow problem in which there is a given demand d(i) for each commodity i = 1,...,k, and one wishes to maximize the fraction α such that a α fraction of each commodity’s demand is met, subject to the joint capacity constraints of the network. It is straightforward to see that the maximum concurrent flow value, α ∗ is at most ρ(S), for any cut S, and hence at most the minimum sparsity ratio: if the total cost (or equivalently, capacity) of S is C, and it disconnects terminal pairs of total demand D, ¯¯ then if one just focuses on these commodities, the maximum fraction of the demand that can be met is at most C/D¯=ρ(S). Since LP duality implies that the maximum con ¯ current flow value is exactly equal to the optimal value of the linear relaxation (5.18)( 5.22), we can reinterpret Theorem 5.2 as the following approximate max-flow-min-cut theorem. THEOREM 5.4 For any instance with k terminal pairs, the minimum sparsity ratio is always at least the maximum concurrent flow value, and is always at most O(logk)times as much. Throughout this section, we have ignored the question of computing an optimal solution to the linear relaxation (5.18)-(5.22) and its dual, the maximum concurrent flow problem, (5.33)-(5.36). As for the maximum multicommodity flow problem, there are three distinct options. First, one can give polynomial-sized LP reformulations. Second, one can apply the ellipsoid algorithm. And finally, we will see that the maximum con current flow problem can be easily formulated as fractional packing problem. To give a fractional packing formulation of this problem, we first make a simple change of variables, where maximizing α is replaced by minimizing a variable λ, which corresponds to 1/α. This results in the following equivalent linear program. minimize λ (5.37) subject to k i=1 P∈Pi P∈Pi (e) f (P)= d(i), f (P)≤ λc(e), f (P)≥ 0, for each i = 1,...,k, for each e ∈ E, for each P ∈ Pi , i = 1,...,k. (5.38) (5.39) (5.40) The most natural way to formulate this as a fractional packing problem is to let Q denote the set of flows f satisfying the demand constraints (5.38) and the non-negativity constraints (5.40), and to let the packing constraints Az ≤ λb correspond to the capacity constraints (5.39). However, one obtains a more efficient algorithm by also adding to Q the constraints that each commodity alone must not violate the given capacity constraint. f (P)≤ c(e), for each e ∈ E, i = 1,...,k. (5.41) P∈Pi(e) It is easy to see that, even with these additional constraints, the two linear programs (5.33)-(5.36) and (5.37)-(5.41) are equivalent. However, by strengthening Q in this way, the width of the formulation can now be bounded by k, since for each f ∈ Q, the total flow on each edge e can be at most kc(e). Furthermore, the required subroutine to optimize over Q is still relatively easy: it requires k (single-commodity) maximum flow computations. By incorporating randomization as first proposed by Klein, Plotkin, Stein, & Tardos [KPST94], the effort for this step can be reduced to, in effect, a single max flow computation. This algorithm for the maximum concurrent flow problem is due to Leighton, Makedon, Plotkin, Stein, Tardos, & Tragoudas [LMP+95]. Finally, the dual variables maintained by this algorithm can be easily adapted to yield the required near- optimal solution for (5.18)-(5.22). MINIMUM FEEDBACK ARC SETS AND RELATED PROBLEMS 5.4 The techniques described in the previous two sections were limited to undirected graphs. Leighton & Rao [LR88] also considered a rather special case in which the graphs are directed: they were able to extend Theorem 5.4, which bounds the ratio between the optimal values to the maximum concurrent flow and the sparsest cut problems, to the case in which there is a unit-demand commodity between each (ordered) pair of vertices. One 5.4 MINIMUM FEEDBACK ARC SETS AND RELATED PROBLEMS 27 of the primary applications of this generalization is an O(log2 n)-approximation algorithm for the minimum-cost feedback arc set in directed graphs. This was improved by Seymour [Sey95], who gave an O(logn loglogn)-approximation algorithm. His algorithm is quite similar in spirit to the techniques that we have described in the previous two sections, and hence we shall give his result, even though it does not explicitly rely on any connection to multicommodity flow problems. We shall present a more intuitive description of Seymour’s result that is due to [ENRS95]. Even, Naor, Rao, & Schieber [ENRS95] have also extended this approach to yield similarly improved performance guarantees for a number of other problems. 5.4.1 AN LP-BASED APPROXIMATION ALGORITHM A feedback arc set in a directed graph G =(V, A) is a subset of arcs F ⊆A, such that if all arcs in F are deleted, the remaining graph (V, A −F) is acyclic. Equivalently, we can require that for each cycle C in G, at least one arc of C is contained in F.Inthe minimum-cost feedback arc set problem, we are given a directed graph G =(V, E),a cost c(a) for each arc a ∈A, and we wish to find a feedback arc set F of minimum total cost a∈Fc(a). It is straightforward to show that the minimum-cost feedback arc set problem in directed graphs is equivalent to the minimum-cost feedback vertex set problem in directed graphs (where the aim is to delete a cheap set of vertices so that no cycle remains), in that any performance guarantee obtained for one problem would translate into the same guarantee for the other. Hence, we see that there is a dramatic difference between our current knowledge for the minimum-cost feedback vertex set problem in undirected and directed graphs (see Chapter 9). We are given a directed graph G =(V, A), and a cost c(a) for each arc a ∈A.We shall assume, without loss of generality, that each cost c(a) is a positive integer. Let C denote the set of all cycles in G. We can formulate the minimum-cost feedback arc set problem as the following integer programming problem: minimize c(a)x(a) a∈A (5.42) subject to In its linear relaxx(a) ≥1, a∈C x(a) ∈{0,1}, ation, we replace (5.44) witfor each C ∈C, for each a ∈A. h (5.43) (5.44) x(a) ≥0, for each a ∈A. (5.45) Seymour’s algorithm, which we call Feedback, has the following outline: solve the linear relaxation (5.42), (5.43), & (5.45) and then interpret the optimal fractional solution x ∗as a length function for the arcs; use the length function to compute a partition of the nodes (V1,V2) (in a way to be specified later), delete all arcs from V1 to V2 or vice versa (whichever is cheaper), and recurse on the graphs induced by V1 and V2. Of course, in order to initiate this approach, one must observe that the linear program can be solved in polynomial time by the ellipsoid algorithm, since the separation problem required is essentially an all-pairs shortest path computation [GLS88]. Alternatively, one can obtain a more efficient algorithm by formulating the problem as a fractional covering problem, and then applying the algorithm of Plotkin, Shmoys, & Tardos [PST95]. From this outline, it is clear that the key to the performance bound is the way in which the graph is partitioned. Let φ denote the value of the optimal fractional solution ∗ x . Furthermore, for a subset of vertices S, let G[S] denote the subgraph of G induced by S; that is, the graph with vertex set S and arc set A[S] ={(u,v): (u,v)∈A, u,v ∈S.}. Finally, let δ+(S) ={(u,v) : (u,v) ∈ A, u ∈S,v ∈ S¯}, and analogously, let δ−(S) = {(v,u) : (v,u)∈A, u ∈S,v ∈S¯}. LEMMA 5.7 For a given strongly connected directed graph G =(V,A), suppose that there exists a feasible solution x to (5.43) and (5.45) of objective function value φ. There exists a partition (S,S) of V such that, for some ,0 <<1, the following three con ¯ ditions hold: c(a)x(a)≤ φ; (5.46) a∈A[S] c(a)x(a)≤(1 − )φ; a∈A[ ¯S] (5.47) and either c(a)≤20 φlog(1/ )loglogφ (5.48) a∈δ+(S) or c(a)≤20 φlog(1/ )loglogφ. (5.49) a∈δ−(S) Furthermore, this partition can be found in polynomial time. We will first show that Lemma 5.7 suffices to show that Feedback has the claimed performance guarantee, and then give its proof. We should note there is some slack in the constant given in Lemma 5.7 (that is, 20), and that we are not attempting to give the best constant that is obtainable via this line of proof. 5.4.2 ANALYZING THE ALGORITHM FEEDBACK We next show that Feedback is an O(logn loglogn)-approximation algorithm for the minimum-cost feedback arc set in directed graphs (see Figure 5.6). In computing a feedback arc set, a natural first step is to partition the graph into its strongly connected components. Since each cycle is contained in some strongly connected component, we can solve each component separately, and obtain a solution for the original graph by taking the union of the solutions found for the components. Of course, one need only consider the non-trivial strongly connected components; for example, if a graph is acyclic, each strongly connected component consists of a single vertex, and the empty set is a feedback 5.4 MINIMUM FEEDBACK ARC SETS AND RELATED PROBLEMS 29 function Feedback(G,x) if G is acyclic then return ∅; else find strongly connected components C of G; for each non-trivial strongly connected component C ∈ C S ←Feedback-Cut(C, x) if c(e) ≤ c(e) e∈δ+ (S) e∈δ−(S) then F ← δ+(S) else F ← δ−(S); let G1 and G2 be the graphs induced by S and V (G)− S; return F∪Feedback(G1 ,x)∪Feedback(G2 ,x) FIGURE 5.6 The algorithm Feedback arc set. We can view the input to the algorithm Feedback as the graph G, the cost function c, and a feasible solution x to the linear relaxation (5.43) and (5.45). First, we compute the strongly connected components of G. For each non-trivial component, we apply Lemma 5.7 to partition its vertex set into S and S¯ . Either the arcs from S to S¯ are added to the feedback arc set, or those from S¯ to S, whichever is cheaper. We apply the algorithm recursively to each of G[S] and G[S¯]; it is useful to note that, for any subgraph of G, the restriction of x to its arcs is a feasible solution to its linear relaxation. The recursion stops when the input is acyclic. It is clear that the algorithm finds a feasible feedback arc set. As observed above, we can assume without loss of generality that the input is strongly connected. Let F(φ) denote the maximum value of the cost of a solution produced by the algorithm when given a graph and a feasible fractional solution of cost at most φ.By Lemma 5.7, we see that the function F obeys the following recurrence relation: F(φ) ≤ max {F( φ) + F((1 − )φ) + 20 φ log(1/)loglogφ}; 0<<1 F(φ) = 0if φ< 1. We shall prove by induction on φ that this implies that F(φ) ≤ 20φ logφ loglogφ. (5.50) The claim is clearly true for φ = 0, since the existence of a feasible fractional solution of cost 0 implies that the graph is acyclic. Let ¯= 1 − . Since φ and ¯φ are both less than φ, we apply the inductive hypothesis to the recurrence relation to get that F(φ) ≤ max {20 φ log( φ)loglog( φ) + 0<<1 20¯φ log(¯φ)loglog(¯φ) + 20 φ log(1/)loglogφ} ≤ max {20 φ(logφ − log(1/ ))loglogφ + 0<<1 20¯φ logφ loglogφ + 20 φ log(1/)loglogφ} = 20φ logφ loglogφ ∗ If we apply the algorithm with an optimal fractional solution x , its objective function value φ ∗ is a lower bound on the integer optimum; hence we have shown that the algorithm is a 20logφ ∗ loglogφ ∗-approximation algorithm. As was observed in [ENSS95], the following standard ideas allow this to be converted to an O(logn loglogn)-approximation algorithm. The main idea is that we use an optimal fractional solution x ∗ to round and rescale the weights for an equivalent input so that the new fractional optimal value is upper bounded by a polynomial in n. First observe that the ratio between the optimal integer value and the optimal fractional value ∗ is at most n. To see this, take the optimal fractional solution x , and for each a ∈ A, set x¯(a)= 1if x ∗ (a)≥ 1/n, and set x¯(a)= 0 otherwise. This is a feasible integer solution, since for any cycle C ∈ C, there must exist some arc a ∈ C such that x ∗ (a)≥ 1/n. Hence, each arc such that c(a)> nφ ∗ is not in any optimal feedback arc set. This implies that we can contract each such edge and obtain an equivalent instance. Furthermore, if we include each arc a such that c(a)<φ ∗ /m in our feedback arc set, then the total cost of these arcs is at most φ ∗ . If we delete these arcs and apply a ρapproximation algorithm to the resulting graph, the sum of the total costs of the deleted arcs and of the solution found is at most ρ+1 times the optimum. Furthermore, we can now round down each cost c(a)to its nearest integral multiple of φ ∗ /m, and then rescale by dividing φ ∗ /m to obtain a new input, in which each cost is an integer between 0 and nm. The rescaling changes only the units in which the costs are expressed, and the rounding down can introduce an error of at most φ ∗ . Hence, if we apply a ρ-approximation algorithm to our modified data, we obtain a solution of cost within a factor of ρ+ 2of optimal. Hence, we have achieved our goal of reducing the problem to instances in which φ ∗ can be bounded by a polynomial in n. THEOREM 5.5 Given an optimal fractional solution x ∗ of value φ ∗ , Feedback is an O(logφ ∗ loglogφ ∗ )-approximation algorithm, and by preprocessing the input, yields an O(logn loglogn)-approximation algorithm for the minimum-cost feedback arc set problem in directed graphs. One corollary of Theorem 5.5 is that the ratio between the optimal value of the integer program (5.42)–(5.44), and its linear relaxation is O(logφ ∗ loglogφ ∗ ). Alon and Seymour [Sey95] have shown that there are instances for which this ratio is (logφ ∗ ). Consequently, in order to improve this algorithm by more than a loglogφ ∗ factor, it will be necessary to rely on a stronger lower bound. 5.4.3 FINDING A GOOD PARTITION We return now to the proof of Lemma 5.7. The algorithm to find the claimed cut is quite similar to the one used in the proof of Theorem 5.1. As in the proof of that theorem, we can think of the graph G, the length function x, and the cost function c as defining a system of pipes: for each (u,v) ∈ A, there is a (one-way) pipe from u to v of length x(u,v)and cross-section area c(u,v). Hence, the objective function value φcorresponds to the total volume in the system. Let distx (u,v)denote the length of the shortest path from u to vin G with respect to 5.4 MINIMUM FEEDBACK ARC SETS AND RELATED PROBLEMS 31 the arc-length function x. For a given vertex vˆ∈V , we can compute the set of vertices reachable from vˆwithin a given radius r: B+(v,ˆ r) ={u ∈V : distx (v,ˆ u) ≤r}. (5.51) x Analogously, let B−(v,ˆ r) ={u ∈V : distx (u,v)ˆ≤r}. Furthermore, we can compute the x total volume of the pipe system that is contained within a radius r of vertex vˆ: V +(v,ˆ r) = c(u,v)x(u,v)+ c(u,v)(r −distx (v,ˆ u)) (5.52) u,v∈Bx +(v,ˆ r)(u,v)∈δ+(Bx +(v,ˆ r)) and V −(v,ˆ r) c(u,v)x(u,v)+ v)). (5.53) = c(u,v)(r −distx (v, ˆ u,v∈Bx −(v,ˆ r)(u,v)∈δ−(Bx −(v,ˆ r)) Throughout the remainder of this section, we will omit the explicit reference to the particular length function x in our notation, with the understanding that it should be understood unambiguously. Given the graph G, its cost function c, and a length function x of objective function value φ, we select a vertex vˆand then consider a sequence of radii from vˆ. For each radius r, we can consider the cuts defined by setting S to B+(v,ˆ r) or to B−(v,ˆ r); in the former case, we aim to bound the cost of δ+(S), whereas in the latter we aim to bound the cost of δ−(S). For the purpose of the proof, we shall consider radii defined in the following way. We let the initial radius r =1/8. While V +(v,ˆ r) ≤φ/2, we define an increment 1 d(r) =; 10log(φ/V +(v,ˆ r))loglogφ If V +(v,ˆ r +d(r)) < 2V +(v,ˆ r), then we claim that we can identify a good cut of the form S = v,ρ), where r ≤ρ ≤r +d(r). If the volume repeatedly doubles until the B+(ˆ volume captured exceeds φ/2, then we enter a second phase in which the analogous steps are taken with respect to V −(v,ˆ r) and B−(v,ˆ r). To complete the proof of the lemma, we need to establish three claims: (1) if the volume does not double, then we can identify a good cut; (2) the volume cannot expand beyond φ/2 in both phases; (3) the good cut is of a form that is easy to compute. To prove the first claim, it is useful to recall some facts about the behavior of the the function V +(v,ˆ r) for a fixed vertex vˆ. If there does not exist a vertex u such that distx (v,ˆ u) =r, then this function is differentiable at r, and its derivative is equal to the total cost of the cut defined by the current radius r: c(u,v). (u,v)∈δ+(B+(v,ˆ r)) So the function consists of fewer than n linear pieces. There might be discontinuities at the breakpoints, each of which corresponds to a vertex at the prescribed distance from vˆ. However, it is a non-decreasing function of r. Hence, if we have identified an interval [r,r +d] over which the volume increases by at most ν, there must exist a point within that interval at which the derivative is at most ν/d, and hence there is a cut of a total cost at most ν/d. Suppose that we have found a radius r¯for which V +(v,ˆ r¯+d(r¯))<2V +(v,ˆ r¯). Hence, the increase in volume over this range is less than V +(v,ˆ r¯), and so the overall rate of increase is less than V +(v,ˆ r¯)φ =10V +(v,ˆ r¯)log loglogφ. d(r¯) V +(v,ˆ r¯) Let ρ, r¯≤ρ ≤¯r +d(r¯), denote a value of r for which ∂V +(v,ˆ r)φ < 10V +(v,ˆ r¯)log loglogφ, ∂rV +(v,ˆ r¯) and let S =B+(ˆ v,ρ). We shall show S satisfies the properties required by the lemma. Let = v,ρ)/φ. V +(ˆ Since V +(v,ˆ r¯) ≤V + v,ρ) = φ ≤2V +(ˆ r ), (ˆ v, ¯ we have that c(a) ≤10 φlog(2/)loglogφ; a∈δ+(S) applying the crudest of estimates, we see that the cost of the cut defined by S attains the claimed bound. Furthermore, the objective function value of x restricted to the arcs A[S] is at most the volume V +(ˆ φ. On the other hand, the objective v,ρ); hence, this is at most function value of x restricted to the arcs A[S¯] is at most the volume φ−V +(ˆ v,ρ); hence, this is at most ¯φ. Repeating the analogous argument with respect to V − , we see that a cut S found in either phase satisfies the conditions of the lemma. We next turn to the proof of the second claim, that at some point in the two phases, we find some interval [r,r +d(r)] for which the volume does not double. We shall assume, for a contradiction, that this is not the case, and then show that this assumption implies that there exists a directed cycle C of length a∈Cx(a) is less than 1; this contradicts the fact that x is a feasible solution to the linear relaxation. In fact, we will show that there exists some vertex uˆsuch that distx (ˆ v) < 1/2 and distx (ˆ u)< 1/2. u, ˆ v, ˆ First, we compute an upper bound on the final radius computed in the first phase; that is, the radius rˆsuch that V +(v,ˆ rˆ)> φ/2 that causes the phase to end. To give an upper bound on rˆ, we upper bound the increments d(r) computed along the way. For each increment d(r) computed, there is a corresponding volume V +(v,ˆ r), where 1/8 ≤ V +(v,ˆ r) ≤φ/2. Since the volume doubles with each iteration, at most one of these values lies in the interval (φ/2 +1,φ/2 ], for each =1,..., logφ +4. If there is an increment that corresponds to the interval (φ/4,φ/2], then it is at most 11 =; (10log(φ/(φ/2))loglogφ) (10loglogφ) the increment corresponding to the interval (φ/2 +1,φ/2 ]is atmost1/(10 loglogφ). Hence, we see that logφ +4 1 111 rˆ≤+ =+ H( logφ +4). (5.54) 8 =1 10 loglogφ 8 10loglogφ Using even the crudest estimates, it is easy to verify that this implies that rˆ< 1/2. The identical calculation also shows that if the second phase does not end until the current radius yields a volume greater than φ/2, then the final radius for the second phase 5.5 FINDING BALANCED CUTS AND OTHER APPLICATIONS 33 is less than 1/2. However, between the two phases, more than φ units of volume have been captured. Since there are only φ units of volume overall, some part of the pipe system must be captured in both phases. But then, there must exist some vertex uˆ such that distx (v,ˆˆ u, ˆ u)< 1/2 and distx (ˆ v) < 1/2. This contradicts the fact that x is a feasible solution to the linear relaxation. Hence, in one of the two phases, we must indentify a good cut. Finally, we must argue that we can find a good cut. For any cut S, it is straightforward to check if there exists some for which conditions (5.46)-(5.48) hold. We have already shown that there exists a good cut of the form B−(ˆ v,ρ). However, for any v,ρ) or B+(ˆ given vˆ, there are at most n distinct cuts the form B+(ˆ v,ρ): one need only consider ρ = dist(ˆ v,ρ). Hence, the algorithm v,v) for some v ∈V . Of course, the same is true for B−(ˆ Feedback-Cut, used in the algorithm Feedback, need only enumerate these cuts until it finds a good one (see Figure 5.7). Note that we can give a much better implementation of Feedback-Cut by considering the vertices v in order of their distance from vˆ; this implies that the algorithm is just a slight modification to Dijkstra’s algorithm for the single-source shortest path problem (see, for example, the textbook of Cormen, Leiserson, and Rivest [CLR90]): Dijkstra’s algorithm repeatedly identifies the next closest vertex to a given vertex vˆ, and hence continually maintains a cut S of the appropriate form; after finding the next closest vertex to vˆ, we need only check if the current S satisfies the conditions of Lemma 5.7. FINDING BALANCED CUTS AND OTHER APPLICATIONS 5.5 While the sparsest cut problem is of interest in its own right, it is just the starting point for a host of applications. In particular, we will show how a subroutine that produces sparse cuts can be used to compute near-optimal balanced cuts; the approximation algorithm for the balanced cut problem can then be used in a variety of settings to derive divideand- conquer approximation algorithms. function Feedback-Cut(G,x) fix vˆ∈V ; for each v ∈V −{ˆv}S ←{u ∈V : distx (v,ˆ u) ≤distx (ˆ v,v)}; if S satisfies (5.46)-(5.48) then return S; T ←{u ∈V : distx (u,v)ˆ≤distx (v,v)ˆ}; if T satisfies (5.46),(5.47), & (5.48) then return T . FIGURE 5.7 The algorithm Feedback-Cut 5.5.1 FINDING BALANCED CUTS In the α-balanced cut problem, we are given an undirected graph G =(V, E), where each edge e ∈E has a positive cost c(e);an α-balanced cut is a subset of vertices S ⊆V such that αn ≤|S|≤(1 −α)n, where n =|V |, and the objective is to find such a cut for which its total cost, c(e), is minimized. Let Cα denote the total cost of the e∈δ(S) optimal α-balanced cut. The special case in which α =1/2 is sometimes referred to as the graph bisection problem. We have already discussed in Section 5.1 that an approximation algorithm for this problem can be quite useful in designing divide-and-conquer approximation algorithms. We shall next show that the algorithm of Section 5.3 for the sparsest cut problem can be used in this setting. Given an instance of the α-balanced cut problem, we can construct an instance of n the sparsest cut problem by letting there be 2 terminal pairs, one for each pair of vertices u,v ∈V , and setting the demand of each commodity to be 1; we shall call this the all-pairs unit-demand problem. For any cut S ⊆V , its sparsity ratio ρ(S) is equal to the ratio of its total cost c(e) to |S||V −S|, since the latter quantity is the total e∈δ(S) demand of terminal pairs that are disconnected by deleting the edges in δ(S). This denominator is made large by keeping S and V −S of roughly the same size; that is, the cut is balanced. In fact, if S is α-balanced, then the denominator is at least n2α(1 −α), and hence the sparsity ratio is at most Cα/[n2α(1−α)]. Of course, the sparsity ratio need not be minimized by finding the cheapest balanced cut: there might be very imbalanced cuts for which the total cost is sufficiently small so as to offset the fact that the denominator is smaller. The greedy set covering algorithm computes a cover by repeatedly choosing a set which is the cheapest per element covered (see Chapter 3 for an analysis of this algorithm). The following algorithm Greedy-Ratio for the α-balanced cut problem is analogous: we repeatedly choose additional vertices to add to a cut S by choosing additional ¯ vertices, for which the cost of the new edges cut per vertex selected is small. We initialize V1 =V ; in general, Vi will denote the set of vertices remaining at the start of the ith iteration of the algorithm. In iteration i, we apply our sparsest cut approximation algorithm to all-pairs unit-demand problem for the graph induced by Vi ; the cut found by this algorithm is a partition of the vertices into two sets Si and Vi −Si , where we shall assume that Si is the smaller of the two. If S =∪i 1 S is such that |S¯|>α|V |, then the ¯ = algorithm terminates. Otherwise, we set Vi+1 =Vi −Si , and the algorithm continues. LEMMA 5.8 For any α ≤1/3, the algorithm Greedy-Ratio finds an α-balanced cut. Proof. The algorithm must clearly halt at some point; let denote the iteration in which it halts. Let k =|∪− 11 Si |. The set S found by the algorithm has size ¯ i= k +|S |≤k +(n −k)/2 ≤n/2 +k/2 <(1 +α)n/2 ≤(1 −α)n. We next turn to showing that the cut found by Greedy-Ratio is near-optimal. We will not show that it is an approximation algorithm in the traditional sense, since we will not compare the cost of the cut found to the optimal α-balanced cut, Cα. Instead, we will 5.5 FINDING BALANCED CUTS AND OTHER APPLICATIONS 35 compare the cost of the α-balanced cut found to the cost of the optimal β-balanced cut, Cβ, where β>α. Since it is more restrictive to require a cut to be β-balanced than to be α-balanced, it is possible that Cβ is much greater than Cα. Before completing the analysis of the performance of this algorithm, we first introduce some notation. The input graph evolves over the course of the execution of the algorithm, as more and more of its vertices are deleted. Thus, a notation such as δ(S) is ambiguous, since it is not clear to which graph we are referring. For any set of vertices S ⊆Vi , we shall let ci (S) = c(e), e∈δi (S) where δi (S) denote the set of edges (u,v) such that u ∈S and v ∈Vi −S. Since V =V1, we will define c(S) =c1(S) for any S ⊆V .If denotes the number of iterations that the algorithm makes, we shall set ni =|Vi |and si =|Si |, for each i =1,..., . THEOREM 5.6 If the Greedy-Ratio algorithm uses a ρ-approximation algorithm to find a sparse cut in each iteration, then, for any β>α, where α ≤1/3, the algorithm finds an α-balanced cut of cost at most 3ρ Cβ. β−α Proof. Let R denote an optimal β-balanced cut in the input G =(V, E). Consider the cut Si found in iteration i, i =1,..., . We know that Ri =R −∪ij − = 11 Sj contains more than (β −α)n vertices; in fact, we also know that Vi −Ri also has this many vertices, and since one of these two sets has size greater than (1 −α)n/2 ≥n/3, we know that the product of their sizes is greater than (β −α)n2/3. Hence, for the graph considered ci (Ri ) in iteration i, the sparsest cut value is at most (β−α)n2/3. This implies that ci (Si ) ci (Ri ) c(R) ≤ρ ·≤ρ · , si (ni −si ) (β −α)n2/3 (β −α)n2/3 and hence, ρCβ ci (Si ) ≤·si . (β −α)n/3 Summing this inequality for i =1,..., , we see that ρCβ 3ρCβ c(S¯) ≤ ci (Si ) ≤·si ≤ . (β −α)n/3 (β −α) i=1 i=1 The relationship between the sparsest cut problem and obtaining a balanced cut was independently discovered by Leighton & Rao [LR88] and Plaisted [Pla90]. By combining Theorem 5.6 with the O(logk)-approximation algorithm for the sparsest cut problem that was given in Section 5.3, we obtain the following corollary. COROLLARY 5.3 For any fixed ,0 ≤≤1/6, there is a polynomial-time algorithm that finds a 1/3-balanced cut of cost within an O(logn) factor of the cost of the optimal 1/3 + -balanced cut. 5.5.2 APPLICATIONS OF BALANCED CUT THEOREMS In Section 5.1, we showed that an algorithm to find near-optimal balanced cuts could be used to derive an approximation algorithm for the minimum cut linear arrangement problem, via a divide-and-conquer approach. In this section, we will consider two other applications of this philosophy. Each of these applications will rely on a good balanced- cut algorithm, but in each case we will need a different sort of balanced cut. However, the techniques discussed in this chapter can be extended to yield the required subroutines. We first consider a problem related to the solution of a linear system of equations Ax = b, where A is a positive-definite symmetric matrix, and we wish to compute x for a given input (A,b). A well-known method for solving such a system of equations is to apply Gaussian elimination. Since we are applying this method to a symmetric positive- definite matrix, we may restrict attention to the variant of Gaussian elimination in which we use only diagonal pivot entries. Furthermore, in each iteration of the algorithm, we maintain a symmetric matrix as we gradually transform the system of equations into an equivalent system (A ,b ) in which A is the identity matrix. In most applications, the matrix A is extremely sparse; that is, most of its entries are zeroes. The processing of A can be made much more efficient if its sparsity can be maintained as it is transformed to A . One very stringent requirement of this type is to require that each 0 in the matrix A should remain a 0 throughout the matrix’s transformation. For example, in the following sequence, we perform Gaussian elimination without introducing any non-zeroes, where the starred element is the pivot element in the current iteration: ⎡ ⎤⎡ ⎤⎡ ⎤⎡ ⎤ 411 310 2∗ 00 1∗ 00 ⎦ ⎦ ⎦ ⎦ 110 → 11∗ 0 → 0 10 → 0 10 . 101∗ 001 001 001 This is a consequence of the order in which we chose the pivot elements. Had we started by pivoting on the 4, we would have obtained the matrix ⎡ 1 0 ⎤ 0 0 3 −1 ⎦. 0 −1 3 If we pivot on the diagonal element att, then the i, jth entry of the new matrix is aij − aitatj/att, i, j = t. Hence, we are assured that no new non-zero is created if we select an index t such that aij = 0 implies that ait = 0or atj = 0, for each i, j = t. (5.55) For simplicity, we shall assume that any non-zero remains a non-zero throughout the computation; in other words, if Gaussian elimination computes an element of the form c− c, where c = 0, then we shall still treat this new element as a non-zero. We shall first focus on the following question: for which symmetric positive-definite matrices A does there exist a sequence of pivots so that no new non-zeroes are created throughout Gaussian elimination. This question has a rather elegant answer. Symmetric matrices can be easily modeled by graphs. For each index 1,...,n create a vertex. For each non-zero entry aij, create the edge (i, j). Note that the fact that the matrix A is symmetric implies that this construction yields an undirected graph. If we consider the 5.5 FINDING BALANCED CUTS AND OTHER APPLICATIONS 37 contrapositive of condition (5.55) and translate this into this graph setting, we see that a pivot can be performed on att without creating a non-zero if there is an edge connecting i and j whenever there are edges (t,i)and (t, j); in other words, the neighbors of vertex t induce a clique in the graph. Hence, a matrix can be reduced to the identity without introducing non-zeroes, whenever the corresponding graph has the following property: the vertices can be ordered v1,...,vn , such that, for each j = 1,...,n −1, the neighbors of vj in {vj+1,...,vn } induce a clique in the original graph. Such an ordering of the vertices is a called a perfect elimination ordering. Hence, we are interested in those graphs which admit a perfect elimination ordering. These graphs can be nicely characterized. They are precisely the class of chordal graphs: those graph for which any cycle of length at least 4 has an edge connecting some pair of vertices that are not consecutive in the cycle (a so- called chord of the cycle). These graphs are also commonly called triangulated graphs. It is beyond the scope of this chapter to prove this characterization of chordal graphs, and the reader is referred to the textbook of Golumbic [Gol80]. However, not all graphs are chordal, and hence in some cases, non-zeroes must be introduced in the process of performing Gaussian elimination. We shall be interested in finding an ordering of pivot elements so that the resulting number of non-zeroes is minimized. We shall this the minimum fill-in problem for symmetric positive-definite matrices. By the previous discussion, this problem is equivalent to the following graph theoretic question: given a graph G = (V,E), find a superset of edges F ⊇ E such that the graph (V,F) is a chordal graph, so that the size of F is as small as possible. We shall call this the minimum chordal extension problem. Yannakakis [Yan81] showed that this problem is NP-complete. Agrawal, Klein, & Ravi [AKR93] focus on the case in which the maximum degree in the given graph is a constant , or equivalently, there are a constant number of nonzeroes in each row of the given matrix. They gave the first approximation algorithm with a non-trivial performance guarantee for this problem, and we shall present the main ideas of this result. This result relies on several sophisticated results on the structure of chordal graphs, and it is beyond the scope of this chapter to prove the correctness and performance of this algorithm. For these results, and for a concise history of research on this problem, the reader is referred to [AKR93]. For a given ordering of the vertices v1,...,vn , we compute a sequence of graphs Gi , i = 0,...,n. The graph G0 is the input graph G. The graph Gi is computed from Gi−1 by adding each edge (vj ,vk ), i < j i. Then the problem can be rephrased as follows: find σ consistent with ≺such that n−1 1 c(e) is minimized. In effect, the minimum cut linear arrangement problem i= e∈Si is the bottleneck (or min-max) version of this min-sum problem (but we are also constrained here to permutations σ that are consistent with ≺). The idea underlying the approximation algorithm of Ravi, Agrawal, & Klein is exactly as for the minimum cut linear arrangement problem. That is, we need to compute a balanced partition of the nodes, and recursively solve the two subproblems. Of course, for the partition to make sense, we need to find a partition of V into S and V −S such that there does not exist an edge (v,u) in G where u ∈S and v ∈V −S; that is, δ−(S) = ∅. Thus, we shall focus on such ≺-consistent cuts S and their corresponding edge sets δ+(S). Once again, we will say that such a cut is α-balanced if αn ≤|S|≤(1 −α)n. The cost of such a cut S is c(e). Ravi, Agrawal, & Klein have observed that the e∈δ+(S) approach of Leighton & Rao can be extended to yield the following theorem. THEOREM 5.9 There is a polynomial-time algorithm to find a 1/4-balanced ≺-consistent cut in a directed acyclic graph of cost within an O(logn) factor of the minimum cost of a 1/3-balanced ≺-consistent cut. The algorithm for the storage-time product minimization problem is quite natural: we apply the algorithm of Theorem 5.9 to the graph to partition the problem into two subproblems. Let A(G) denote the cost of the solution found by the algorithm on input G, and let B(G) denote the cost of the cut S found by the algorithm of Theorem 5.9. Furthermore, let G1 denote the graph induced by S, and let G 2 denote the graph induced by V −S. Since each edge in G is either in G1,in G2, or in the cut δ+(S), we can derive the following recurrence relation: A(G) ≤A(G1) +A(G2) +(n −1)B(G), where the last term is a consequence of the fact that each edge in δ+(S) might occur in each of the n −1 sets Si , i =1,...,n −1. The crux of the analysis of the performance guarantee of this algorithm lies in devising a good lower bound on the optimum. Consider an optimal solution σ ∗ . If we consider any set Si , i = n/3 ,..., 2n/3 , then we see that it defines a 1/3-balanced ≺-consistent cut. Hence, the cost of each of these is at least B∗ , where B∗ is the minimum cost of a 1/3-balanced ≺-consistent cut. Hence nB∗ /3 is a lower bound on the optimal value, OPTS×T (G), and hence we have the recurrence: A(G) ≤A(G1) +A(G2) +O(logn) ·OPTS×T (G). By relying on the fact that each Gi has at most (3/4)n vertices, it is easy to show by induction that A(G) =O(log2 n)OPTS×T (G). It is not hard to extend this argument to give the bound claimed for the general case in which there are arbitrary processing times. This somewhat more general approach to using a balanced cut as a lower bound was first introduced in a different context by Hansen [Han89]. Although we have only given a few examples, there are quite a number of applications for which this approach has led to the first approximation algorithm with polylogarithmic performance guarantee. Leighton & Rao considered several applications from the domain of VLSI design: among these are results for the crossing number of a graph (i.e., embedding a graph in the plane so as to minimize the number of pairs of edges that cross each other in this embedding); and for the problem of laying out a graph in the plane so as to minimize the area required for the layout. Many of these applications were first proposed by Bhatt & Leighton [BL84] who focused attention on obtaining approximation algorithms for the graph bisection problem. CONCLUSIONS 5.6 In this chapter, we have tried to present the highlights of an approach to the design of approximation algorithms that seeks to capitalize on good algorithms for cut problems in order to design and analyze divide-and-conquer algorithms. We have not attempted to catalog all of the work done in this area, and therefore have not discussed a number of closely related results. However, we will briefly mention two of the most prominent areas that we have omitted. The first success in applying divide-and-conquer based on finding good cuts was for the restricted case of planar graphs; as one of the initial applications of their planar separator theorem, Lipton & Tarjan [LT80] observed that one could derive polynomial approximation schemes for a wide variety of combinatorial problems. However, in the subsequent years, Baker [Bak94] has given a better approach for exploiting planarity, and her work is discussed in Chapter 9. Furthermore, we have also omitted discussion of work on better performance guarantees of approximation algorithms for these cut problems when restricted to planar graphs, which includes results of Rao [Rao87], Garg, Saran, & Vazirani [GSV94], Tardos & Vazirani [TV93], and Klein, Plotkin, & Rao [KPR91]. Randomized rounding has also been applied in the context multicut approximation algorithms; Bertsimas, Teo, & Vohra [BV94, BTV95] have given other mathematical programming formulations which are more amenable to this approach. However, the bounds obtained from this approach do not dominate the ones presented here, and in some sense, build on the earlier work. Randomized rounding is extensively discussed in Chapter 11. This area of research is still extremely active, and there is still much work to be done. For example, very little is known about multicommoditymax-flow min-cut bounds when the input graph is directed. Even more importantly, for each of the problems discussed, there is no complexity-theoretic evidence that a significantly better performance guarantee cannot be obtained; in fact, there may well be approximation algorithms with constant performance guarantees. In fact, Chung & Yau [CY94] gave an algorithm for which they claimed such a performance guarantee for the balanced cut problem, but the proof contained in [CY94] is not correct, and a correct proof of this claim has not been published. Finally, it is ironic that the pivotal result in this chapter, Corollary 5.3, which finds a good balanced cut, is not an approximation algorithm in the traditional sense. While this deficiency is unimportant for any of the applications, it would, nonetheless, be an important advance to find a good approximation algorithm for this problem. REFERENCES ACKNOWLEDGEMENTS ´ results in this chapter. I would also like to thank Satish Rao for explaining his insights into Seymour’s algorithm at a time they were still evolving as part of his own research. This chapter benefited greatly from the perceptive comments of Yuval Rabani, David Williamson, Yuri Rabinovich, and this volume’s editor, Dorit Hochbaum. This work was partially supported by NSF grant CCR-9307391. First and foremost, I would to thank Eva Tardos, from whom I first learned most of the REFERENCES [AKR93] A. Agrawal, P. Klein, and R. Ravi. Cutting down on fill using nested dissection: provably good elimination orderings. In: J.A. George, J.R. Gilbert, and J. Liu, editors. Sparse Matrix Computations: Graph Theory Issues and Algorithms, IMA Volumes in Mathematics and Its Applications, Springer-Verlag, New York, 1993, pages 31–55. [AMO93] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network flows: theory, algorithms, and applications. Prentice Hall, Englewood Cliffs, NJ, 1993. [AR95] Y. Aumann and Y. Rabani. An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput., to appear. [AvisD91] D. Avis and M. Deza. The cut cone, L1 embeddability, complexity, and multicommodity flows. Networks, 21:595–617, 1991. [Bak94] B. S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. Assoc. Comput. Mach., 41:153–180, 1994. [BTV95] D. Bertsimas, C. Teo, and R. Vohra. Nonlinear formulations and improved randomized approximation algorithms for multicut problems. In E. Balas and J. Clausen, editors, Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 920, pages 29–40. Springer, 1995. [BV94] D. Bertsimas and R. Vohra. Linear programming relaxations, approximation algorithms, and randomized rounding: a unified approach to covering problems. Working paper #-3654-94 MSA, Sloan School of Management, MIT, Cambridge, MA, 1993. [BL84] S.N. Bhatt and F.T. Leighton. A framework for solving VLSI graph layout problems. J. Comput. Sys. Sciences, 28:300–343, 1984. [Bou85] J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., pages 46–52, 1985. [CY94] F. R. K. Chung and S. T. Yau. A near optimal algorithm for edge separators. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 1–8, 1994. [Chv83] V. Chv´atal. Linear programming. W.H. Freeman, New York, 1983. [CLR90] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press and McGraw Hill, Cambridge, MA and New York, 1990. [DJP+92] E. Dahlhaus, D.S. Johnson, C.H. Papadimitriou, P.D. Seymour, and M. Yannakakis. The complexity of multiway cuts. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 241–251, 1992. [ENRS95] G. Even, J. Naor, S. Rao, and B. Schieber. Divide-and-conquer approximation algorithms via spreading metrics. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pages 62–71, 1995. [ENSS95] G. Even, J. Naor, B. Schieber, and M. Sudan. Approximating minimum feedback sets and multi-cuts in directed graphs. In E. Balas and J. Clausen, editors, Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 920, pages 14–28. Springer, 1995. [FF56] L. R. Ford, Jr. and D. R. Fulkerson. Maximal flow through a network. Canadian J. Math, 8:399–404, 1956. [Gar95] N. Garg. A deterministic O(log k)-approximation algorithm for the sparsest cut problem. Preprint, 1995. [GSV94] N. Garg, H. Saran, and V.V. Vazirani. Finding separator cuts in planar graphs within twice the optimal. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, pages 14–23, 1994. [GK94] M. D. Grigoriadis and L. G. Khachiyan. Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. Optimization, 4:86–107, 1994. [GLS88] M. Gr¨otschel, L. Lov´asz, and A. Schrijver. Geometric algorithms and combinatorial optimization. Springer-Verlag, Berlin, 1988. [Gol80] M.C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980. [GRE84] J.R. Gilbert, D.J. Rose, and A. Edenbrandt. A separator theorem for chordal graphs. SIAM J. Alg. Discrete Methods, 5:306–313, 1984. [GVY93] N. Garg, V. V. Vazirani, and M. Yannakakis. Approximate max-flow min-(multi)cut theorems and their applications. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 698–707, 1993. [Han89] M. Hansen. Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pages 604–609, 1989. [Hu63] T.C. Hu. Multicommodity network flows. Operations Res., 11:344–360, 1963. [Kah93] N. Kahale. On reducing the cut ratio to the multicut problem. Technical Report 93–78, DIMACS, 1993. [Kar84] N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica 4:373–395, 1984. [Kha79] L.G. Khachiyan. A polynomial algorithm in linear programming (in Russian). Doklady Akademiia Nauk SSSR, 244:1093–1096, 1979. English translation: Soviet Mathematics Doklady 20:191–194. [KPR91] P. Klein, S. Plotkin, and S. Rao. Planar graphs, multicommodity flow, and network decomposition. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 682–690, 1991. [KPST94] P. Klein, S. Plotkin, C. Stein, and E. Tardos. Faster approximation algorithms for the ´ unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM J. on Computing, 23:310–321, 1994. [KRAR95] P. Klein, S. Rao, A. Agrawal, and R. Ravi. An approximate max-flow min-cut relation for undirected multicommodity flow, with applications. Combinatorica, REFERENCES 15:187–202, 1995. [LLR95] N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215–246, 1995. [LMP+95] T. Leighton, F. Makedon, S. Plotkin, C. Stein, ´ E. Tardos, and S. Tragoudas. Fast approximation algorithms for multicommodity flow problems. J. Comput. Sys. Sciences, 50:228–243, 1995. [LR88] T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 422–431, 1988. [LR94] F. T. Leighton and S. Rao. An approximation max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. Unpublished manuscript, 1994. [LT80] R.J. Lipton and R.E. Tarjan. Applications of a planar separator theorem. SIAM J. Comput., 9:615–627, 1980. [MR95] R. Motwani and P. Raghavan. Randomized algorithms. Cambridge University Press, Cambridge, 1995. [Pla90] D. Plaisted. A heuristic algorithm for small separators in planar graphs. SIAM J. Comput., 19:267–280, 1990. [PST95] S. A. Plotkin, D. B. Shmoys, and E. Tardos. Fast approximation algorithms for ´ fractional packing and covering problems. Math. Oper. Res., 20:257–301, 1995. [PT95] S. Plotkin and E. Tardos. Improved bounds on the max-flow min-cut ratio for ´ multicommodity flows. Combinatorica, 15:425–434, 1995. [RAK91] R. Ravi, A. Agrawal, and P. Klein. Ordering problems approximated: single-processor scheduling and interval graph completion. In Proceedings of the 18th International Colloquium on Automata, Languages, and Processing, Lecture Notes in Computer Science 510, pages 751–762, 1991. [Rao87] S. Rao. Finding near optimal separators in planar graphs. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, pages 225–237, 1987. [Sey95] P.D. Seymour. Packing directed circuits fractionally. Combinatorica, 15:281–288, 1995. [SM90] F. Shahrokhi and D.W. Matula. The maximum concurrent flow problem. J. Assoc. Comput. Mach., 37:318–334, 1990. [Tra91] S. Tragoudas. VLSI partitioning approximation algorithms based on multicommodity flow and other techniques. PhD thesis, University of Texas, Dallas, 1991. [TV93] E. Tardos and V. V. Vazirani. Improved bounds for the max-flow min-multicut ratio ´ for planar and Kr,r -free graphs. Inform. Proc. Lett., 47:77–80, 1993. [Yan81] M. Yannakakis. Computing the minimum fill-in is NP-complete. SIAM J. Alg. Discrete Methods, 2:77–79, 1981.