# Divide-and-Conquer Approximation Algorithms via Spreading Metrics.

Abstract. We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time. The spreading metric assigns lengths to either edges or vertices of the input graph, such that all subgraphs for which the optimization problem is nontrivial have large diameters. In addition, the spreading metric provides a lower bound, [Tau], on the cost of solving the optimization problem. We present a polynomial time approximation algorithm for problems modeled by our paradigm whose approximation factor is O(min{log [Tau] log log [Tau], log k log log k)), where k denotes the number of "interesting" vertices in the problem instance, and is at most the number of vertices.We present seven problems that can be formulated to fit the paradigm. For all these problems our algorithm improves previous results. The problems are: (1) linear arrangement; (2) embedding a graph in a d-dimensional mesh; (3) interval graph completion; (4) minimizing storage-time product; (5) subset feedback sets in directed graphs and multicuts in circular networks; (6) symmetric multicuts in directed networks; (7) balanced partitions and p-separators (for small values of [Rho]) in directed graphs.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Program Complexity]: Nonnumerical Algorithms and Problems--computations on discrete structures; G.2.2 [Discrete Mathematics]: Graph Theory--graph algorithms; network problems

General Terms: Algorithms, Theory

Additional Key Words and Phrases: Approximation algorithms, divide and conquer, feedback set, linear arrangement, multicut, spreading metrics

1. Introduction

In this paper, we describe efficient divide-and-conquer techniques that yield improved approximation algorithms for a number of NP-Hard graph optimization problems. Our methods rely on a class of functions on graphs, which we call spreading metrics. Informally, a spreading metric on a graph is an assignment of lengths to either its edges or vertices, so that subgraphs in which the optimization problem is nontrivial are spread apart in the associated metric space. The volume of a spreading metric on a graph is defined as the sum, taken over all edges (vertices), of the length of the edges (vertices) multiplied by their capacity. The volume of a spreading metric of a problem instance provides a lower bound on the cost of solving the problem. A spreading metric allows us to apply divide-and-conquer in which the divide step is guided by the volumes of the subproblems rather than traditional methods that divide according to the sizes of the subproblems.

A b-balanced cut in a graph G = (V, E) is a cut that partitions the graph into connected components (strongly connected components in the directed case), each of which contains at most (1 - b) [multiplied by] n vertices, where n = |V|. Leighton and Rao [1999] presented an algorithm that finds a b-balanced cut, for any b [is less than or equal to] 1/3, whose capacity is O(log n) times the minimum capacity of a bisector (a 1/2-balanced cut). Often, when the cost of a minimum capacity b-balanced cut can be used to lower bound the optimal cost of the problem at hand, one can construct a log-square approximation factor algorithm by recursively dividing the problems using b-balanced cuts for some constant b. One logarithmic error term is due to the error in the separator procedure, and the other comes from the recursion depth. On the face of it, it seemed that the only way to "break" the log-square barrier in this framework was by improving the separator approximation.

Our methods allow us to break the log-square barrier by an almost logarithmic factor, without finding better separators than Leighton and Rao [1999]. The idea is that spreading metrics can be used to give an estimate of the recursive cost of solving subproblems that arise as a result of applying divide-and-conquer. Thus, we can manipulate the cost of the cut to be higher when the recursion makes a lot of progress, and lower when it does not. In fact, we can do this to such an extent that we only pay a single logarithmic factor (along with an additional doubly logarithmic factor) for both the recursion and the error in the cut procedure. This generalizes the approach taken in by Seymour [1995] in proving the existence of small feedback sets in directed unweighted graphs. We note that a spreading metric is computed only once, and in all the recursive calls we use the same spreading metric.

Recently, in Even et al. [1999], we were able to extend our spreading metrics technique to graph partitioning problems. We were able to apply a simpler recursion and thus obtain simple logarithmic factor approximation algorithms for balanced partitions and separators. However, the simpler recursion does not apply to the applications described in this paper.

1.1. RESULTS. We consider problems that are amenable to a divide-and-conquer approach and for which a spreading metric is computable in polynomial time. There are two main parameters that are attached to each problem instance. The first one is [Tau], the volume of the spreading metric on the graph. This parameter [Tau] is a lower bound on the cost of the optimal solution and is obtained in this paper by solving a linear program. The second parameter is k, the number of "interesting" vertices. This is defined by the problem instance, and is at most the number of vertices. We present a polynomial time approximation algorithm for several problems where the approximation factor is O(min{log [Tau] log log [Tau], log k log log k}).

We demonstrate the applicability of this approach by describing applications of our methods to seven problems that fit our paradigm. For all of these problems, our approximation algorithm improves upon previous results. These problems are: (1) linear arrangement; (2) embedding a graph in a d-dimensional mesh;(1) (3) interval graph completion; (4) minimizing storage-time product; (5) (subset) feedback sets in directed graphs and multicuts in circular networks; (6) symmetric multicuts in directed networks. (7) q-balanced partitions and p-separators in directed graphs. For the first four problems we improve the approximation factor from O([log.sup.2] n) to O(log n log log n), where n denotes the number of vertices. (For these problems, [Tau] [is greater than or equal to] n and k = n.) For problems (5) and (6), we improve the approximation factor from O(min{log [Tau] log log [Tau], log n log log n, [log.sup.2] k) to O(min{log [Tau] log log [Tau], log k log log k}), where k denotes the size of the subset in the subset feedback set problems or the number of source-sink pairs in the multicut problems. For Problem (7), let [Tau]' denote the optimal cost of a v-separator where v = 1/q in the case of q-balanced partitions or v = [Rho] - [Epsilon], for some fixed [Epsilon], in the [Rho]-separator case. Our approximation algorithm finds a separator whose capacity is O(min{log n log log n, log [Tau]' log log [Tau]'} [multiplied by] [Tau]'). This improves on previous results for the cases in which q is big enough, or when p is small enough.

For some of the applications, for example, subset feedback set in a directed graph, a spreading metric can be obtained from the "natural" linear programming relaxation of the problem. In fact, this type of spreading metrics draws directly from past work on multi-commodity flow and feedback sets in directed graphs, for example, Leighton and Rao [1999], Seymour [1995], and Garg et al. [1996]. However, for other problems, for example, linear arrangement and interval graph completion, computing a spreading metric involves an "indirect" linear programming formulation. The formulation is indirect in the sense that it captures certain properties of an optimal (integral) solution, yet an integral solution (to the formulation) does not provide an integral solution to the original problem, as opposed to standard linear programming relaxations. Nevertheless, the spreading metric obtained from the linear programming formulation still has all the required properties.

Some optimization problems require balanced partitioning for applying a divide-and-conquer approach. However, the cuts we find are not guaranteed to be balanced. We present an additional technique for balancing the decomposition found by recursively finding cuts.

1.2. COMPARISON TO PRIOR WORK. Leighton and Rao [1999] presented an O(log n) approximation algorithm for finding balanced partitions of graphs. Their algorithm is based on an approximation algorithm for a sparse cut, namely, a cut which approximately minimizes the ratio of the weight of the edges in the cut divided by the number of vertices in the smaller side of the cut. Some of the results that follow from this are: a basis for an algorithmic implementation of the decomposition tree framework of Bhatt and Leighton [1984], an O([log.sup.2]n) approximation algorithm for the minimum feedback edge set in directed graphs, and an O([log.sup.2] n) approximation algorithm for the minimum cut linear arrangement problem.

The problems of linear arrangement and graph embeddings in d-dimensional meshes were considered by Hansen [1989]. His algorithms rely on the algorithm of Leighton and Rao [1999] to obtain O([log.sup.2]n) approximation algorithms for these problems. We present a novel linear programming formulation for these problems that enables us to use our paradigm to improve the approximation factor for these problems to O(log n log log n). Ravi et al. [1991] considered a generalization of the linear arrangement problem, called the storage-time product minimization problem. In case the execution time of all tasks is the same, their algorithm achieves an O([log.sup.2]n) approximation factor. Again, our algorithm improves this factor to O(log n log log n).

The problem of finding a super-graph of a given graph, such that the super-graph is an interval graph and contains as few edges as possible, was considered by Ravi et al. [1991]. They extended Hansen's technique for this problem and obtained an O([log.sup.2] n) approximation factor. We present a novel linear programming formulation of this problem that enables us to use our paradigm to obtain an O(log n log log n) approximation factor.

Decompositions of directed graphs were considered in the works of Leighton and Rao [1999], Seymour [1995], Klein et al. [1997], and Even et al. [1998]. Seymour [1995] was the first to present a decomposition algorithm that does not rely on balanced cuts. His paper proves the existence of feedback vertex sets of cardinality O([Tau] log [Tau] log log [Tau]) in unweighted directed graphs. Klein et al. [1997] considered symmetric multicuts in directed graphs. By extending the work of Garg et al. [1996] to the directed case, they obtained an O([log.sup.2] k) approximation factor for this problem. Even et al. [1998] considered the subset feedback set problem in directed graphs, as well as multicuts in circular networks. In the subset feedback set problem, the feedback set is only required to intersect a subset of the directed cycles in the graph, characterized by a distinguished subset of the vertices called special vertices. They presented an O(min{log [Tau] log log [Tau], log n log log n, [log.sup.2.]}) approximation factor for the subset feedback set problem, where k denotes the number of special vertices. The first two terms in the approximation factor were obtained by extending the work of Seymour [1995], and the last term was obtained by extending the work of Garg et al. [1996]. We use our paradigm to obtain an O(min{log k log log k, log [Tau] log log [Tau]}) approximation factor for all of these problems--an improvement over previous work for small values of k.

The [Rho]-separator problem in undirected (directed) graphs is to find a minimum capacity subset of edges whose removal partitions the graph into (strongly) connected components, each of which contains at most [Rho] [multiplied by] n vertices, where n is the total number of vertices. This problem, for both the undirected and the directed cases, was introduced in Even et al. [1999], where a logarithmic approximation factor algorithm is described for the undirected case, and for the directed case when [Rho] [is greater than or equal to] 1/2. The algorithm presented here applies to the directed case for the range [Rho] [is less than] 1/2. It finds a separator whose capacity is O(min{log n log log n, log [Tau]' log log [Tau]') [multiplied by] [Tau]'), where [Tau]' denotes the minimum cost of a v-separator, for some fixed v [is less than] [Rho]. Another problem that we consider is that of computing q-balanced partitions in directed graphs. Here, we are interested in a minimum capacity subset of edges whose removal partitions the graph into strongly connected components that can be grouped into q parts of roughly equal size. We apply our [Rho]-separators algorithm to this problem and achieve an algorithm with the same approximation factor, as detailed in Section 6. Note that one can find a 2v-separator (and hence, also a q-balanced partition) by applying recursively the approximate separator algorithm in Leighton and Rao [1999] until all strongly connected components are small enough. (See also Leighton et al. [1990] and Simon and Teng [1997].) This approach yields a 2v-separator whose capacity is O(log n log(1/v)[Tau]'). Hence, our p-separator algorithm is superior to the recursive one for v [is less than] max{1/log n, [[Tau]'.sup.-log log [Tau]'/log n}]. (A similar improvement is achieved for the q-balanced partitioning problem as detailed in Section 6.)

The recent papers of Linial et al. [1995] and Aumann and Rabani [1998] also consider metrics on graphs. They regard graphs with edge lengths as geometric objects and embed them in a high dimensional space with a logarithmic distortion of the edge lengths. The dimension of the space they map the graphs into is poly-logarithmic, and the "geometry" of the graph is then utilized for approximating multi-cuts. When we embed graphs into a Euclidean space (e.g., d-dimensional meshes), we consider only constant dimensionality. The main property we utilize for finding cuts is that the diameter of every subgraph that corresponds to a nontrivial subproblem is sufficiently large.

The rest of the paper is organized as follows. Section 2 describes the approximation paradigm and states its performance. Section 3 gives an algorithm for partitioning a large diameter graph. This partitioning algorithm is used in the divide step of the divide-and-conquer algorithm described in Section 4. Section 5 extends the divide-and-conquer algorithm to problems where the divide step has to partition the graph into balanced parts. Finally, Section 6 describes the applications of the algorithm.

2. The Approximation Paradigm

In this section, we describe our approximation paradigm and state its performance. For simplicity, we define the paradigm for undirected graphs, and consider the edge version. We later show how to extend the paradigm to directed graphs and to the vertex version.

2.1. WHAT KIND OF PROBLEMS CAN WE APPROXIMATE? The paradigm finds approximate solutions of minimization problems on undirected graphs with edge capacities. A problem instance is represented by a pair of graphs (G, H), where G = (V, E, c) is a graph with edge capacities c(e) [is greater than or equal to] 1, for every edge e [element of] E. The graph H = (V, [E.sub.H]), called the auxiliary graph, is defined on the same vertex set as G. The auxiliary graph is often a clique, for example, the linear arrangement problem, or a (partial) matching between pairs of terminals, for example, multicuts in directed circular networks.

Depending on the problem, we define a real-valued function scaler over the subgraphs of H. Let G' and H' denote subgraphs of G and H, respectively, defined over the same vertex set. We require that if H' contains edges, then scaler(H') [is greater than or equal to] 1, otherwise scaler(H') = 0. The graph H and the scaler function have the following roles:

(1) If H' lacks edges (i.e., scaler(H') = 0), then the subproblem (G', H') is trivial (i.e., can be solved with zero cost).

(2) scaler(H') is used in quantifying the cost of dividing the problem (G', H') into subproblems, as discussed in the paragraph on divide-and-conquer applicability.

(3) scaler(H') serves as a lower bound on the diameter of G' induced by a spreading metric, as discussed in the paragraph on spreading metric applicability.

In all the applications discussed herein, the scaler function depends only on the size of the largest connected component in H (e.g., scaler(H) equals the size of the largest connected component in H).

We can approximate problems that satisfy two properties: divide-and-conquer applicability and spreading metric applicability, defined below.

2.1.1. Divide-and-Conquer Applicability. In general, divide-and-conquer applicability means that a problem can be solved by dividing it into subproblems, solving each subproblem independently, and then merging the solutions to obtain a solution for the original problem. For our paradigm we also require that the cost of merging the solutions is proportional to capacities of cuts in G as defined below. The definition of divide-and-conquer applicability in this paper is based on a decomposition tree representation, where a decomposition tree specifies a set of solutions to a problem instance. There is a cost associated with a decomposition tree which is an upper bound on the cost of every solution specified by it. We define a decomposition tree as follows:

Definition 1. A decomposition tree T of a graph G(V, E) is a tree in with the following properties.

(1) Every tree node corresponds to a subset of the vertices V. Denote the subset of vertices corresponding to a tree node t [element of] T by [V.sub.t].

(2) The subset of vertices corresponding to the tree root r [element of] T is [V.sub.r] = V.

(3) For every tree node t [element of] T, the set [V.sub.t] is partitioned by the sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the children of t.

Let t [element of] T denote a node in a decomposition tree T. Let [G.sub.t] and [H.sub.t] denote the subgraphs of G and H, respectively, that are induced by [V.sub.t]. We now define what it means that a decomposition tree T fully decomposes the problem represented by (G,H).

Definition 2. A decomposition tree T of G(V, E) fully decomposes the problem (G, H) if for every leaf t [element of] T, the problem ([G.sub.t], [H.sub.t]) is trivial.

Note that the translation of a decomposition tree that fully decomposes a problem instance to an actual solution of the problem instance depends on how solutions for subproblems are merged to a solution for the whole problem. This varies from one problem to another. For example, in the linear arrangement problem, a solution induced by a decomposition tree is an ordering of the vertices in their order of appearance as leaves of the decomposition tree. In all our applications, this translation is simple and can be computed in polynomial time. We elaborate more on this point in Section 6.

Every internal node t [element of] T in the decomposition tree defines a cut in G as follows: Let [t.sub.1], ..., [t.sub.d] denote the children of t. The cut corresponding to t is the set of edges [F.sub.t] [subset or equal to] E that have endpoints in different subsets [V.sub.t] and [V.sub.t]. Let c([F.sub.t]) denote the sum of the edge capacities in [F.sub.t].

For our approximation paradigm to apply, we require that the cost of merging solutions of the subproblems represented by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to a solution of the problem ([G.sub.t], [H.sub.t]) depends on c([F.sub.t]) scaled by the coefficient scaler([H.sub.t]). The sum of all these costs constitutes the cost of T as defined below.

Definition 3. Let T denote a decomposition tree that fully decomposes a problem (G, H). The cost of T equals the sum of the scaled capacities of the cuts corresponding to the internal decomposition tree nodes. Formally,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The cost of a decomposition tree that fully decomposes a problem instance bounds the cost of every solution of the problem instance that is built up from the decomposition tree. Thus, if we can obtain a low-cost decomposition tree that fully decomposes a problem instance, then we can also find low-cost solutions of the problem instance.

2.1.2. Spreading Metric Applicability. Spreading metric applicability means that for the problem (G, H) there exists a spreading metric, defined as follows:

Definition 4. A spreading metric is a function l: E [right arrow] [R.sup.+] that assigns nonnegative lengths to every edge e [element of] E. This function must satisfy the following two properties:

Lower-bound: The volume of the spreading metric, defined by [[Gamma].sub.e [element of] E] c(e)f(e), is a lower bound on the cost of every solution of the problem (G,H).

Diameter guarantee: The distance induced by the spreading metric "spreads" the graph and all its subgraphs that correspond to nontrivial subproblems. More precisely, for vertices u and v, let [dist.sub.l](u, v) denote the length of the shortest path from u to v, where distances are measured with respect to edge lengths l(e). Let U [subset or equal to] V be any subset of the vertex set. Denote by [G.sub.U] and [H.sub.U] the subgraphs of G and H induced by U, respectively. The diameter guarantee requires that for every subset U [subset or equal to] V, there exist two vertices u, v [element of] U for which [dist.sub.l](u, v) [is greater than or equal to] scaler([H.sub.U]).

2.2. THE GENERIC APPROXIMATION ALGORITHM. The generic approximation algorithm is depicted in Figure 1. The partitioning procedure partition is described in Section 3. First, a spreading metric for (G, H) is computed. Then, a divide-and-conquer algorithm partitions the graph recursively until the subproblems defined by the resulting subgraphs are trivial. The generic approximation computes a decomposition tree that is translated to a solution of the problem.

FIG. 1. The generic approximation algorithm. divide&conquer (G, H, l) begin If [E.sub.H] is empty, then T = [Phi] else /* divide */ ([V.sub.1], [V.sub.2]) = partition(G, H, l) For i = 1,2 do Let [G.sub.i] and [H.sub.i] denote the subgraphs of G and H induced by [V.sub.i]. [T.sub.i] = divide&conquer([G.sub.i], [H.sub.i], [l.sub.i]) Let T denote a tree with a root t such that: [V.sub.t] = V (G); and t has two children: the root of [T.sub.1] and the root of [T.sub.2]. return(T) end generic_approximation_alg(G, H) begin Compute a spreading metric l : E [right arrow] Q. T = divide&conquer(G,H,l) Return(T) end

2.3. THE MAIN RESULT. The main result presented in this paper is the following theorem:

THEOREM 1. Let (G, H) denote an optimization problem that satisfies the paradigm defined in Section 2.1. If a spreading metric is computable in polynomial time, then the generic approximation algorithm finds, in polynomial time, a decomposition tree that fully decomposes the problem (G, H), the cost of which is O([Tau] min{log [Tau] log log [Tau], log k log log k}), where [Tau] is the cost of the spreading metric (and hence a lower bound on the cost of an optimal solution), and k [is less than or equal to] n is the number of nonisolated vertices in H (i.e., vertices with positive degree).

Recall that the cost of a decomposition tree that fully decomposes a problem instance is an upper bound on the cost of all the solutions that are specified by the decomposition tree. Moreover, a solution specified by a decomposition tree can be computed in polynomial time. The following corollary follows from Theorem 1.

COROLLARY 2. Under the premises of Theorem 1, the generic approximation algorithm finds in polynomial time a solution of problem (G, H), the cost of which is O([Tau] min {log [Tau] log log [Tau], log k log log k}).

2.4. EXTENSIONS: VERTEX VERSION AND DIRECTED GRAPHS

(1) In the "vertex" version of this paradigm: (i) the capacity function c(v) is associated with each vertex v [element of] V, rather than each edge; (ii) the problem is partitioned in the divide step by removing vertices rather than edges; and (iii) the spreading metric assigns labels to the vertices. The vertex version is applied in Section 6.4.

(2) The paradigm can be applied to directed graphs as well (see Sections 6.5-6.7). The modification for the directed case is that partitioning in the directed case means dividing the graph into strongly connected components instead of connected components. This means that a directed cut is attached to each divide step rather than a undirected cut.

(3) When the auxiliary graph is directed as well, the radius guarantee refers to distances (measured in G) between two vertices: a "source" and a "sink" in the auxiliary graph.

2.5. REMARKS

(1) For some problems, an additional balance constraint is required for applying a divide-and-conquer paradigm. The balance constraint requires that all the values [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are bounded from above by a constant fraction of scaler(H). In applications where the auxiliary graph H is a complete graph and the scaler function depends only on the cardinality of the vertex set in the auxiliary graph, then the balance constraint translates to the constraint that the cut used is a b-balanced cut, for some b [is greater than] 1/2. In Section 5, we extend our algorithms to deal with balance constraints.

(2) If [H.sub.U] contains at least one edge, then the diameter guarantee together with the assumptions that c(e) [is greater than or equal to] 1, and that the cost scaler is at least one, imply that the volume [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Therefore, the volume of a spreading metric of a non-trivial problem is at least 1.

(3) Suppose that the volume of the spreading metric satisfies the lower bound property, however, the diameter guarantee only satisfies [dist.sub.l](u, v) [is greater than or equal to] [Alpha] [multiplied by] scaler([H.sub.U]), where [Alpha] [is less than or equal to] 1 is some parameter (constant or nonconstant). The approximation factor obtained in this case is multiplied by a factor of 1/[Alpha], since the spreading metric can be scaled by a factor of 1/[Alpha], yielding that the volume of the spreading metric (or lower bound guarantee) is also multiplied by a factor of 1/[Alpha].

3. Partitioning High-Diameter Graphs

The main step in the divide-and-conquer procedure is the partitioning step. Loosely speaking, the partitioning procedure searches for a subset of nodes U that satisfies two properties: (a) the volume associated with U is at most half the volume of G; and (b) the capacity of the cut (U, V - U) is comparable with the volume associated with U. These two properties are essential for analyzing the cost of the solution, since one can charge the cost of separating U from the rest of the graph to the volume associated with U. We note that edge lengths remain the same during the recursive calls to the partitioning procedure.

3.1. GENERAL SETTING AND NOTATION. Let G = (V, E) denote a (connected) graph with edge capacities c(e) [is greater than or equal to] 1 for all e [element of] E. Given a subset U [subset] V, let c(U) denote the capacity of the cut (U, V - U). Let H = (V, [E.sub.H]) denote the auxiliary graph corresponding to G, and let l(e) denote the spreading metric that assigns non-negative edge lengths. Let vol(G) denote the volume [[Sigma].sub.e [element of] E] c(e) [multiplied by] l(e). Let u, u' [element of] V be two vertices that belong to the same connected component in the auxiliary graph H, and for which the diameter property guarantees [Delta] ?? [dist.sub.l] (u, u') [is greater than or equal to] scaler(H).

Define N(u, r) by

N(u, r) ?? {v [element of] V: [dist.sub.l](u, v) [is less than] r}

Note the strict inequality in the definition on N(u, r), namely, a vertex v of distance r from u is not in N(u, r).

Denote by E(u, r) the set of edges for which both endpoints belong to N(u, r), and by F(u, r) the set of edges belonging to the cut (N(u, r), V - N(u, r)). Define vol(u, r), the volume of N(u, r), to be:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If vol(u, [Delta]/2) [is greater than] vol(G)/2, then we reverse the roles of u and u' and consider N(u', [Delta]/2). Since N(u, [Delta]/2) and N(u', [Delta]/2) are disjoint, it follows that vol(u', [Delta]/2) [is less than or equal to] vol(G)/2. Hence, we may assume without loss of generality that vol(u, [Delta]/2) [is less than or equal to] vol(G)/2.

3.2. THE PARTITIONING PROCEDURE. The partitioning procedure grows a region N(u, r) using a single-source shortest-path algorithm until the capacity of the cut [Gamma](u, r) is bounded by an expression justified by Theorem 3. The partitioning procedure is depicted in Figure 2.

3.3. EXISTENCE OF A GOOD CUT. We now prove a theorem that shows the existence of a good cut. Loosely speaking, a corollary to this theorem is that the partitioning procedure stops with a radius r [is less than or equal to] [Delta]/2.

THEOREM 3. Let G = (V, E) denote a graph with edge capacities c(e) [is greater than or equal to] 1 and nonnegative edge lengths l(e). Let u and u' in V be two vertices such that [dist.sub.l](u, u') = [Delta]. For any [r.sub.0], [r.sub.1] satisfying 0 [is less than] [r.sub.0] [is less than] [r.sub.1] [is less than] [Delta], there exists a radius

FIG. 2. The partitioning procedure. partition (G, H, l) begin Choose a pair of vertices u, u' such that: 1. u and u' belong to the same connected component in H; 2. [Delta] = [dist.sub.l](u, u') [is greater than or equal to] scaler(H); and 3. vol(u, [Delta]/2) [is less than or equal to] vol(G)/2 U = N(u, [Delta]/4) (set the initial region) v = closest vertex to U in V - U. let r = [dist.sub.l](u, v) (set initial radius) while c(U) [is greater than] 4/[Delta] [multiplied by] vol(u,r) ln (evol(G)/2vol(u, r)) [multiplied by] ln ln (evol(G)/2vol(u, [Delta]/4)) do begin (grow the region) U = U [union] {v} v = closest vertex to U in V - U. r = [dist.sub.l](u, v) (update radius) end Return (U, V- U) end

[r.sub.0] [is less than or equal to] r [is less than or equal to] [r.sub.1] such that

(1) c(N(u, r)) [is less than or equal to] vol(u, r)/[r.sub.1] - [r.sub.0]ln(e [multiplied by] vol(u, [r.sub.1])/vol(u, r))ln ln(e [multiplied by] vol(u, [r.sub.1])/vol(u, [r.sub.0]).

(The base of all logarithms is e.)

PROOF. We prove the theorem using two lemmata: The first lemma, that follows Seymour [1995] and was used in a discrete fashion by Leighton and Rao [1999] shows that, except for at most n - 1 points, the derivative of the volume function, dvol(u, r)/dr, equals c(N(u, r)). The second lemma, along the lines of Seymour [1995] shows that there exists a radius r [element of] ([r.sub.0], [r.sub.1]) for which dvol(u, r)/dr is not greater than the right-hand side of Eq. (1).

LEMMA 4. Let I = [{[dist.sub.l](u, v)}.sub.v [element of] V]. Then for every r [element of] [[r.sub.0], [r.sub.1]] - I, the derivative dvol(u, r)/dr is defined and satisfies

(2) dvol(u, r)/dr = c(N(u,r)). Lemma 4 follows by observing that in an interval (r', r") in which no new vertices are encountered (i.e., N(u, r') = N(u, r")), the function vol(u, r) is linear.

LEMMA 5. Let f: [[r.sub.0], [r.sub.1]] [right arrow] R be a nonnegative monotone increasing function that is differentiable almost everywhere. If the derivative f' is continuous almost everywhere, then there exists an r [element of] ([r.sub.0], [r.sub.1]) such that f'(r) is defined and satisfies

(3) f'(r) [is less than or equal to] f(r)/[r.sub.1] - [r.sub.0] [multiplied by] ln(e [multiplied by] f([r.sub.1])/f(r)) [multiplied by] ln ln(e [multiplied by] f([r.sub.1])/f([r.sub.0])).

PROOF. By contradiction, suppose that for every r [element of] ([r.sub.0], [r.sub.1])

f'(r) [is greater than] f(r)/[r.sub.1] - [r.sub.0] [multiplied by] ln(e [multiplied by] f([r.sub.1])/f(r)) [multiplied by] ln ln(e [multiplied by] f([r.sub.1])/f([r.sub.0])).

Then,

(4) f'(r)/f(r) [multiplied by] ln(e [multiplied by] f([r.sub.1])/f(r)) [is greater than] 1/[r.sub.1] - [r.sub.0] [multiplied by] ln ln(e [multiplied by] f([r.sub.1]/f([r.sub.0])).

We now integrate both sides over the interval ([r.sub.0], [r.sub.1]). (This can be done since f' is continuous almost everywhere.) Since the right-hand side does not depend on r, we get that after integration the right hand side satisfies:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

To integrate the left-hand side, one may verify by differentiation that

[integral of] f'(r)/f(r) [multiplied by] ln (e [multiplied by] f([r.sub.1])/f(r)) dr = -ln ln(e [multiplied by] f([r.sub.1])/f(r)).

Therefore,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The contradiction now follows, since before we integrated both sides of Eq. (4), the left-hand side was greater than the right-hand side almost everywhere. However, after integration both sides are equal. The lemma follows. []

The proof of Theorem 3 follows by considering the function f(r) = vol(u, r) and applying the two lemmata. []

3.3.1. The Correctness of the Partitioning Algorithm. Theorem 3 proves the existence of a "good" radius in the interval ([Delta]/4, [Delta]/2). This follows by assigning [r.sub.0] = [Delta]/4, [r.sub.1] = [Delta]/2, and the assumption that vol(u, [Delta/2) [is less than or equal to] vol(G)/2. However, the partitioning algorithm only considers radii from the set I = [{[dist.sub.l](u, v)}.sub.v[element of]V]. To prove that the partitioning procedure stops with a "good" radius, we need to show that I contains a "good" radius.

LEMMA 6. There exists a radius r' [element of] I that satisfies Eq. (1).

PROOF. Let r [element of] ([Delta]/4, [Delta]/2) be the radius that satisfies Eq. (1). The existence of such a radius is guaranteed by Theorem 3. Let r' denote the result of rounding the radius r up to the nearest radius in I. Note that N(u, r') = N(u, r), and therefore, c(N(u, r')) = c(N(u, r)). Since the function x ln(ea/x) is increasing in the interval (0, a], the radius r' also satisfies Eq. (1). []

Recall that the analysis of the approximation factor relies on the assumption that the cut is defined by a sphere N(u, r) for which vol(u, r) [is less than or equal to] vol(G)/2. Since the partitioning procedure only considers radii from the set I, it may happen that the radius r' returned by the procedure is greater than [Delta]/2. (This would happen when r [element of] ([Delta]/4, [Delta]/2) is rounded up to r' [is greater than] [Delta]/2.) In this case it is not guaranteed that vol(u, r') [is less than or equal to] vol(G)/2. The following lemma shows that if r' [is greater than] [Delta]/2, then using a radius of [Delta]/2 would result with the same cut. Therefore, either vol(u, r') [is less than or equal to] vol(u, [Delta]/2) [is less than or equal to] vol(G)/2 or we may use (only) in the analysis r' = [Delta]/2.

LEMMA 7. If the procedure returns a radius r' [is greater than] [Delta]/2, then N(u, r') = N(u, [Delta]/2).

PROOF. Recall that r' is the result of rounding a radius r' [is greater than] [Delta]/2 up to a radius r' [element of] I. Hence, for all r [is less than or equal to] t [is less than or equal to] r, N(u, t) = N(u, r'). []

4. Analysis of the Approximation Factor

In this section, we prove Theorem 1. We show that the cost of the decomposition tree T computed by the generic algorithm is O([Tau]- min{log [Tau] log log [Tau], log k log log k}), where [Tau] is the cost of the spreading metric (and hence a lower bound on the cost of an optimal solution), and k [is less than or equal to] n is the number of nonisolated vertices in H (i.e., vertices with positive degree). The proofs of the two approximation factors are given separately below.

4.1. AN O(log [Tau] log log [Tau]) APPROXIMATION FACTOR. The analysis in this case follows the analysis by Seymour [1995]. Consider an internal tree node t [element of] T. The cut [F.sub.t] partitions the vertex subset [V.sub.t] into [V.sub.l] and [V.sub.r], where l and r denote the children of t. Let vol([G.sub.t]) denote the volume of the subgraph [G.sub.t] according to the spreading metric computed in the first step. Recall that the cut [F.sub.t] is computed by choosing a nonisolated vertex u in [H.sub.t] and growing a sphere of radius r' in [G.sub.t] centered at u. Let [vol.sub.l] denote the volume vol(u, r"), where r" = min{r', [Delta]/2}. Lemma 7 implies that [V.sub.l] = N(u, r"). Note that [vol.sub.l] includes, in addition to the volume of the subgraph of [G.sub.t] induced by [V.sub.l], also a contribution from the edges of the cut [F.sub.t]. The assumption that vol(u, [Delta]/2) [is less than or equal to] vol(G)/2 implies that [vol.sub.l] [is less than or equal to] vol(G)/2.

The cost associated with an internal tree node t [element of] T is scaler([H.sub.t]) [multiplied by] c([F.sub.t]). Since scaler([H.sub.t]) [is less than or equal to] [Delta], Theorem 3 implies that

scaler([H.sub.t]) [multiplied by] c([F.sub.t]) [is less than or equal to] 4[vol.sub.l]ln(e [multiplied by] vol([G.sub.t])/2[vol.sub.l])ln ln(e [multiplied by] vol([G.sub.t])/2vol(u, [Delta]/4).

Since the capacity of every edge is at least one and since [Delta] [is greater than or equal to] 1, it follows that vol(u, [Delta]/4) [is greater than or equal to] 1/4. Therefore, the "ln ln" factor is bounded by O(log log vol(G)). For simplicity, we henceforth ignore this "In ln" factor and take it into account only at the end of the analysis.

Let f(x) denote the maximum cost of a decomposition tree of a problem (G, H) for which vol(G) [is less than or equal to] x. From Theorem 3, it follows that the function f(x) satisfies the following recurrence equation

f(x + y) [is less than or equal to] f(x) + f(y) + 4x ln(e(x+y)/2x),

where 1/4 [is less than or equal to] x [is less than or equal to] y. Remark 2 in Section 2.5 implies that if x [is less than] 1, then f(x) = 0.

Define the function F(x) over the interval [1/4, [infinity]) as follows:

F(x) ?? 1/ln(2) [multiplied by] 4x ln(4x).

Note that for 1/4 [is less than or equal to] x [is less than or equal to] y

F(x + y) - F(x) - F(y) [is greater than or equal to] 1/ln(2) [multiplied by] 4x ln(x + y/x).

To show that the function F(x) is a solution of the recurrence equation, we only need to verify that

1/ln(2) [multiplied by] 4x ln(x + y/x) [is greater than or equal to] 4x ln(e(x + y)/2x).

This follows since

ln(e/2) = (1/ln 2 - 1)ln 2 [is less than or equal to] (1/ln 2 - 1)ln(x + y/x).

We conclude that the generic approximation algorithm finds a decomposition tree the cost of which is bounded by F(vol(G)) [multiplied by] ln ln(2e [multiplied by] vol(G)) = O(vol(G) [multiplied by] log(vol(G)) [multiplied by] log log(vol(G))). Since vol(G) is a lower bound on the cost of an optimal solution to the problem (G, H), the first approximation factor follows.

4.2. AN O(log k log log k) APPROXIMATION FACTOR. The generic approximation algorithm needs to be tuned to obtain the O(log k log log k) approximation factor. There are two modifications:

(1) The definition of the volume used for partitioning the graph. We assign a weight of vol(G)/k to every vertex that is nonisolated in H (all other vertices are assigned zero weight). The modified volume of a sphere N(u, r) is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that vol'(G) = 2vol(G).

(2) The range of radii in which the cut is searched for is set to [0, [Delta]/2] (as opposed to [[Delta]/4, [Delta]/2] in the previous analysis).

Let t [element of] T denote an internal tree node. Using the same notation used for the first approximation factor, the implication of these changes is that the cost associated with the cut [F.sub.t] is

scaler([H.sub.t]) [multiplied by] c([F.sub.t]) [is less than or equal to] 2[vol'.sub.l] ln (e [multiplied by] vol'([G.sub.t])/2[vol'.sub.l]ln ln(e [multiplied by] vol'([G.sub.t])/2vol(G)/k).

We now bound the In In factor as follows:

ln ln(e [multiplied by] vol'([G.sub.t])/2vol(G)/k). [is less than or equal to] ln ln(ke).

Again, we ignore the "ln ln" factor till the end of the analysis.

Let f(x) denote the maximum cost of a decomposition tree of a problem (G, H) for which vol'(G) [is less than or equal to] x. The function f(x) satisfies the following recurrence equation

f(x + y) [is less than or equal to] f(x)+ f(y) + 2x ln(e(x + y)/2x),

where vol(G)/k [is less than or equal to] x [is less than or equal to] y. Note that if x [is less than] vol(G)/k, then f(x) = 0 since the subgraph lacks nonisolated vertices.

Define the function F(x) over the interval [vol(G)/k, [infinity) as follows:

F(x) ?? 1/ln 2 [multiplied by] 2x ln(x/vol(G)/k).

The proof that the function F(x) is a solution of the recurrence equation bounding the growth of the function f(x) follows the proof of the first approximation factor.

We conclude that the generic approximation algorithm finds a decomposition tree the cost of which is bounded by F(vol'(G)) [multiplied by] ln ln(ke) = O(vol(G) [multiplied by] log k [multiplied by] log log k), and the second approximation factor follows.

5. Balancing Decomposition Trees

In this section, we show how to derive a balanced decomposition tree from an unbalanced decomposition tree with only a constant multiplicative factor increase in the cost of the tree. Thus, in the case where only a balanced decomposition tree can specify a solution to the problems at hand, we can first find an unbalanced decomposition tree, and then balance it. To simplify the exposition, we assume that the auxiliary graph H is a clique graph on V and that scaler(H') depends only on the number of vertices in H'. We assume further that scaler(H') is monotone non-decreasing and bounded by a polynomial in the number of vertices in H'. All these assumptions hold for our applications (e.g., graph embeddings in d-dimensions).

Definition 5. Let n(t) denote |[V.sub.t]| for an internal tree node t. A tree node t is balanced if for every child [t.sub.i] of t, n([t.sub.i]) [is less than or equal to] (2/3) [multiplied by] n(t). A tree T is balanced if every internal tree node t [element of] T is balanced.

Given an unbalanced tree T, we construct a balanced tree T' from T. Loosely speaking, the balanced tree T' is constructed from T in a top-down fashion, namely, we balance the tree nodes from the root to the leaves. An internal tree node t is balanced by cutting off "small" subtrees from "large" subtrees rooted at children of t. The cut off subtrees are then "promoted" and become children of t. More formally, a subtree rooted at [t.sub.i] is small if n([t.sub.i]) [is less than or equal to] (2/3) [multiplied by] n(t) and large otherwise. The balancing of an internal tree node t proceeds by traversing large subtrees rooted at children of t in preorder (i.e., first the node and then recursively its children). As soon as a small subtree is reached, this small subtree is promoted to become a child of t. A traversal of a large subtree and cutting off of small subtrees from its continues until this subtree becomes small. After the balancing procedure is applied to t, it is applied to the children of t. We note that: (a) When the balancing procedure is applied to t, n(t) does not change. However, n(t) may decrease when the balancing procedure is applied to an ancestor of t. (b) The balanced tree T' may not be a binary tree even if T is. If a balanced and binary decomposition tree is sought, then children [t.sub.1], [t.sub.2] of t [element of] T' for which n([t.sub.1]) [is less than or equal to] n([t.sub.2]) [is less than or equal to] (1/3)n(t) may be coalesced to make T' a binary tree without rendering T' unbalanced. The set of children of the tree node obtained by coalescing [t.sub.1] and [t.sub.2] is the union of the children of [t.sub.1] and [t.sub.2]. Such a coalescing of siblings can be applied in preorder to make T' a balanced binary tree.

Our assumption that the auxiliary graph H is a clique spanning all the vertices, implies that every edge belongs to a cut in the decomposition tree, namely, [[Union].sub.t [element of] T] [F.sub.t] = [[Union].sub.t' [element of] T'] [F.sub.t']= E. For an edge e [element of] E, let t(e) denote the tree node in T whose cut contains e. Namely, t(e) is the least common ancestor in T of the endpoints of e. Similarly, define t'(e) relative to the balanced tree T'. The following lemma shows that n(t'(e))/n(t(e)) is bounded by a constant.

LEMMA 8. For every edge e [element of] E, 2/3 [multiplied by] n(t'(e)) [is less than] n(t(e)).

PROOF. Fix an edge e = (u, v) and assume that the leaf corresponding to u precedes the leaf corresponding to v in preorder traversal. If n(t'(e)) in the beginning of the balancing of t'(e) is not greater than n(t(e)) (in T), then n(t'(e)) [is less than or equal to] n(t(e)) also after the balancing of T, and the lemma follows.

Suppose that at the beginning of the balancing of t'(e), n(t'(e)) [is greater than] n(t(e)). Figure 3 depicts this situation. Since the subtree rooted at t'(e) at the beginning of the balancing of t'(e) is isomorphic to a subtree of T, and since u and v are leaves of this subtree, it follows that t(e) is a descendent of t'(e) at the beginning of the balancing of t'(e). Let [t.sub.u] denote a descendent of t(e) that is promoted to become a child of t'(e) for which [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that such a node must exist since the subtree rooted at t(e) is large (otherwise, t'(e) would have been the same as t(e)), and u precedes v in the preorder traversal that starts at t(e). Since t(e) was not promoted, it follows that n(t(e)) [is greater than] (2/3) [multiplied by] n(t'(e)), and the claim follows. []

[Figure 3 ILLUSTRATION OMITTED]

By our assumptions scaler(H') depends only on the number of vertices in H'. Thus, the function scaler can be viewed as a function defined over the natural numbers. Since scaler(x) is assumed to be monotone nondecreasing and bounded by a polynomial, the value

[Beta] ?? [sup.sub.x [element of] N+]{scaler(x)/scaler(?? (2/3) [multiplied by] x ??)}

is a well-defined constant. We are now ready to prove that the cost of the balanced decomposition tree T' almost equals the cost of an unbalanced decomposition tree T.

THEOREM 9. Assume that: (a) the auxiliary graph H is a clique; and (b) scaler(H') depends only on the number of vertices in H' and is monotone nondecreasing and bounded by a polynomial in the number of vertices in H'.

Let T denote a decomposition tree and let T' denote the balanced decomposition tree obtained by the balancing procedure. Then

cost(T') [is less than or equal to] [Beta] [multiplied by] cost(T).

PROOF. Lemma 8, the fact that scaler([multiplied by]) is monotone non-decreasing, and the definition of [Beta], imply that for every edge e [element of] E,

scaler(n(t'(e)))/scaler(n(t(e))) [is less than or equal to] scaler(n(t'(e)))/scaler(?? (2/3) [multiplied by] n(t'(e)) ??) [is less than or equal to [Beta].

Hence,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] []

6. Applications

In this section we present seven optimization problems to which we apply our paradigm. For each problem, we dedicate a subsection in which we define the problem and show how to cast it in the paradigm of Section 2. The spreading metrics for the various problems are computed by formulating an appropriate linear programming relaxation. We first explain how to solve these linear programs optimally in polynomial time.

6.1. POLYNOMIAL-TIME SOLVABILITY. Let G = (V, E) be a graph, directed or undirected, let c([multiplied by]) be a capacity function associated with the edge set E. A spreading metric attaches lengths [{l(e)}.sub.e [element of] E], to the edges. Denote by dist(u, v) the distance from u to v with respect to the metric induced by l([multiplied by]).

Our linear programming formulations fall into one of two generic categories according to the structure of the auxiliary graph H. For the subset feedback set problem, the multicut problem in directed graphs, and the symmetric multicut problem in directed graphs, the auxiliary graph H is a set of edges that match pairs of terminals. In this case, scaler(H) = 1. This means that the spreading metric linear program attaches lengths to the edges, such that the distance between pairs of terminals is at least one, while minimizing the volume of the graph. This version of spreading metrics draws directly from past work on multicommodity flow and feedback sets in directed graphs, for example, Leighton and Rao [1999], Seymour [1995], and Garg et al. [1996]. Thus, the linear program has the following form.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

s.t. For each pair of terminals t, t: dist(t, t') [is greater than or equal to] 1 [inverted] Ae [element of] E: l(e) [is greater than or equal to] 0

The linear program can be solved optimally in polynomial-time using the Ellipsoid algorithm [Grotschel et al. 1988]. This follows by observing that for a given solution, a shortest path computation between each pair of terminals can determine that, either, all constraints are satisfied, or discover a violated constraint. More on compact formulations of such linear programs and efficient solutions of such linear programs can be found in Shmoys [1997] and Even et al. [1998].

The following problems have an auxiliary graph H which is a clique: linear arrangement, embedding a graph in a d-dimensional mesh, interval graph completion, minimizing storage-time product, q-balanced partitions and [Rho]-separators in directed graphs. Here, scaler(H) depends on the number of vertices in H. Consider the following linear program.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that the linear program guarantees the diameter of every subset U [subset or equal to] V by introducing an "averaging" constraint. Namely, the diameter of U measured from v is at least f(|U|)/(|U| - 1). Hence, the diameter guarantee is satisfied if(|U|) is defined by f(|U|) = (|U| - 1) [multiplied by] scaler([H.sub.U]).

An optimal solution to the linear program can be computed in polynomial time using the Ellipsoid Algorithm [Grotschel et al. 1988]. This follows by observing that for a given candidate solution, we can determine that either all constraints are satisfied, or discover a violated constraint. We run a single-source shortest paths algorithm from every vertex v, and check that for all values of k, 1 [is less than or equal to] k [is less than or equal to] |V|, the k closest vertices to v satisfy the appropriate constraint in the linear program. More details on efficient solutions of such linear programs can be found in Shmoys [1997] and Even et al. [1998].

6.2. LINEAR ARRANGEMENT. The linear arrangement problem is defined as follows:

Input: An undirected graph G = (V, E) with a capacity c(e) associated with each edge e [element of] E.

Output: A linear arrangement of the vertices h: V [right arrow] {1, ..., |V|}, that minimizes the total edge lengths, that is, [[Sigma].sub.e=(i,j) [element of] E]c(e) [multiplied by] |h(i) - h(j)|.

In the context of VLSI layout, |h(i) - h(j)| is referred to as the length of the interconnection between i and j. Finding an optimal linear arrangement is NP-hard. (See Garey and Johnson 1979, problem GT42, p. 200].)

We show how to cast this problem in our paradigm. The graph H = (V, [E.sub.H]) associated with G = (V, E) is the clique graph [C.sub.|V|], and the scaler function is defined by scaler(H = (V, [E.sub.H])) ?? |V| - 1. To establish the divide-and-conquer applicability we consider any binary decomposition tree T that fully decomposes the problem. Note that there is a 1-1 correspondence between the leaves of T and the vertices of G. The solution to the linear arrangement problem that is represented by T is given by arranging the vertices of G in the order of their appearance as leaves of T. The cost of the tree T is cost(T) = [[Sigma].sub.t [element of] T](|[V.sub.t]| - 1)c([F.sub.t]), where [V.sub.t] and [F.sub.t] are the set of vertices and cut corresponding to the tree node t. We need to show that this cost bounds the cost of solutions built up from T. For this we prove that for every tree node t the cost of the subtree rooted at t, denoted [T.sub.t], bounds the cost of solutions built up from [T.sub.t] to the linear arrangement problem for the subgraph of G induced by the set of vertices [V.sub.t]. We prove the claim by induction on the level of the tree nodes. The claim clearly holds for all leaves of T. Consider an internal tree node t [element of] T and denote its two children by [t.sub.L] and [t.sub.R]. By induction the claim holds for both [t.sub.L] and [t.sub.R]. The solution represented by [T.sub.t] is given by concatenating the solutions represented by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that the additional cost is at most |[V.sub.t]| - 1 = scaler([H.sub.t]) times the capacity of the cut [F.sub.t] that separates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We ge

cost([T.sub.t]) [is less than or equal to] cost([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) + cost([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) + (|[V.sub.t]| - 1) [multiplied by] c([F.sub.t]).

The inductive claim follows.

We now show how to compute the spreading metric. Consider the following linear program:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[inverted] Ae [element of] E: l(e) [is greater than or equal to] 0

In the linear program, we follow our previous notation that regards l(e) as edge lengths, and [dist.sub.l](u, v) is the length of the shortest path from u to v.

LEMMA 10. Let e(e) denote a feasible solution of the linear program. For every subset U [subset or equal to] V (|U| [is greater than] 1), and for every vertex v [element of] U there is a vertex u [element of U for which [dist.sub.l](u, v) [is greater than or equal to] 1/4(|U| - 1).

PROOF. The average distance of a node u [element of] U - {v} from v is greater than (1/4)(|U| - 1), because of the constraint corresponding to U and v. Therefore, there exists a vertex u [element of] U whose distance from v is at least the average distance from v, and the lemma follows. []

Note that the previous lemma comes short of the "diameter guarantee" by a factor of 4: while the "diameter guarantee" requires that the diameter of a subset U be greater than scaler([H.sub.U]), the proven bound is only scaler([H.sub.U])/4. As stated in Section 2.5 in Remark 3, this only affects the constant in the approximation factor.

In the next lemma, we prove that the volume of an optimal solution of the linear program satisfies the lower bound property.

LEMMA 11. The cost of an optimal solution of the linear program is a lower bound on the cost of an optimal linear arrangement of G.

PROOF. Consider a linear arrangement h: V [right arrow] {1, ..., |V|} of G. Define l(e) = |h(i) - h(j)| for e = (i,j) [element of] E. We show that l(e) is a feasible solution. Clearly, the cost [[Sigma].sub.e [element of] E]c(e) [multiplied by] l(e) equals the cost of the linear arrangement h. The feasibility of l([multiplied by]) is proved as follows: Consider a subset U [subset or equal to] V, and a vertex v [element of] U. We observe that the average distance from v of the vertices in U is minimized when U is "packed" around v. Now, let [U.sub.L] denote the vertices of U who are to the left of v, namely, [U.sub.L] ?? {u [element of] U:h(u) [is less than] h(v)}. Similarly, define [U.sub.R] ?? {u [element of] U:h(u) [is greater than] h(v)}. Now,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence, l([multiplied by]) is a feasible solution and the lemma follows. []

Note that a binary decomposition tree specifies [2.sup.n-1] solutions to the linear arrangement problem, depending on the orientations of the internal tree nodes (i.e., determining for each internal node which child is the left child). Our approximation algorithm constructs a decomposition tree such that every solution specified by the decomposition tree approximates the optimal linear arrangement. In Bar-Yehuda et al. [1998], a polynomial time algorithm that finds one of the best solutions to the linear arrangement problem among the solutions that are specified by a given decomposition tree is presented.

6.3. GRAPH EMBEDDINGS IN d-DIMENSIONS. The second graph embedding problem we consider is graph embedding in d-dimensional meshes defined as follows:

Input: An undirected graph G = (V, E) with capacity c(e) associated with each edge e [element of] E.

Output: A one-to-one mapping, h, of G to a subgraph containing |V| vertices of the d-dimensional mesh. The value of the embedding is [[Sigma].sub.(u,v) [element of] E]d(h(u), h(v)), where d(x, y) is the number of mesh-edges in the shortest path between x and y in the mesh.

A related graph embedding problem we consider is linear arrangement with d-dimensional cost.

Input: An undirected graph G = (V, E) with capacity c(e) associated with each edge e [element of] E.

Output: A linear arrangement of the vertices h: V [right arrow] {1, ..., |V|}, that minimizes the total d-dimensional edge cost, that is, [[Sigma].sub.e=(i,j) [element of] E]c(e) [multiplied by] [|h(i) - h(j)|.sup.1/d].

We refer to the cost function in the latter problem as the d-dimensional cost of a linear ordering. The following lemma reduces the problem of graph embeddings in d-dimensional meshes to the problem of linear arrangement with d-dimensional cost.

LEMMA 12. Given a linear ordering of G of d-dimensional cost A, one can produce an embedding in the d-dimensional mesh of G of cost-value O(d [multiplied by] A).

PROOF SKETCH. This follows directly from the existence of a curve through a d-dimensional mesh, in which any two vertices that differ by k along the curve are at distance O([dk.sup.1/d]) in the d-dimensional mesh. Given a linear ordering we transform it to an embedding in the d-dimensional mesh by mapping the linear order to such a curve and then by mapping each vertex on the curve to its corresponding point in the d-dimensional mesh. It is easy to see that the property of the curve implies that the cost of the embedding in the d-dimensional mesh is at most O(d) times the d-dimensional cost of the linear ordering. A Peano curve is an example of such a curve. See Sagan [1994] for a description of space filling curves. []

Note that due to Lemma 12, the dimensionality of the mesh, namely d, increases the approximation factor by a linear factor in d. From now on we consider the problem of linear arrangement with d-dimensional cost.

We define the auxiliary graph H = (V, [E.sub.H]) associated with G = (V, E) to be the clique graph [C.sub.|V|, and the scaler function by scaler(H) ?? [(|V| - 1).sup.1/d]. Clearly, if H contains no edges, then |V| = 1 and the problem (G, H) is trivial with cost(G, H) = 0. As in the linear arrangement problem, to establish the divide-and-conquer applicability we consider any binary decomposition tree T that fully decomposes the problem. The solution to the linear arrangement problem with d dimensional cost that is represented by T is given by arranging the vertices of G in the order of their appearance as leaves of T. The cost of the tree T is cost(T) = [[Sigma].sub.t [element of] T[(|V.sub.t]|.sup.1/d]c([F.sub.t]). To show that this cost bounds the cost of the solution represented by T, we prove that for every tree node t the cost of [T.sub.t] bounds the cost of the solution represented by [T.sub.t]. As before, we prove the claim by induction on the level of the tree nodes. The claim clearly holds for all leaves of T. Consider an internal tree node t [element of] T and denote its two children by [t.sub.L] and [t.sub.R]. By induction the claim holds for both [t.sub.L] and [t.sub.R]. The solution represented by [T.sub.t] is given by concatenating the solutions represented by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that the additional cost is at most [(|[V.sub.t]| - 1).sup.1/d] = scaler([H.sub.t]) times the capacity of the cut [F.sub.t]. We get

cost([T.sub.t]) [is less than or equal to] cost([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) + cost([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) + [(|[V.sub.t]| - 1).sup.1/d] [multiplied by] c([F.sub.t]).

The inductive claim follows.

The spreading metric is obtained by solving the following linear program.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[inverted] Ae [element of] E: l(e) [is greater than or equal to] 0

The following lemma is analogous to Lemma 10, and proves that the diameter guarantee is satisfied up to a constant of 4.

LEMMA 13. Let l(e) denote a feasible solution of the linear program. For every subset U [subset or equal to] V (|U| [is greater than] 1), and for every vertex v [element of] U there is a vertex u [element of] U for which [dist.sub.l](u, v) [is greater than or equal to] (1/4) [multiplied by] [(|U| - 1).sup.1/d]

The following lemma is analogous to Lemma 11, and proves that the lower bound property is satisfied.

LEMMA 14. The cost of an optimal solution of the linear program is a lower bound on the cost of a minimum d-dimensional cost of any linear ordering of G.

PROOF. The proof follows the proof of Lemma 11. Consider a linear ordering h([multiplied by]) of the vertices of G. For every edge (i, j) E [element of], define l(i, j) to be [|h(j) - h(i)|.sup.1/d]. Clearly, the cost [[Sigma].sub.e [element of] E]c(e) [multiplied by] l(e) equals the d-dimensional cost of the embedding h([multiplied by]). The feasibility of l([multiplied by]) is proved as follows. Consider a subset U [subset or equal to] V, and a vertex v [element of] U. Vertices in U are at integral distances from v and at most two vertices are at any particular distance. We can thus derive the following inequality.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

Remark. An alternative method for finding a d-dimensional embedding is by following Hansen [1989] technique. However, this requires finding a balanced partitioning of the graph so as to maintain a constant aspect ratio of the meshes in the recursive calls. This can be done using balanced decomposition trees that are presented in Section 5.

6.4. MINIMIZING STORAGE-TIME PRODUCT. Following Ravi et al. [1991], we consider the storage-time product minimization. To make the presentation clearer we consider here only the special case in which all tasks require unit time. However, our algorithm applies also to the more general case where the times differ.

Input: A directed acyclic graph G = (V, E) with edge capacities c(e). The vertices of G represent tasks to be scheduled. An edge e = (u [right arrow] v) with capacity c(e) corresponds to c(e) units of storage generated by task u and consumed by task v.

Output: A linear ordering h: V [right arrow] {1, ..., |V|} of the vertices such that if (u [right arrow] v) [element of] E, then h(u) [is less than] h(v). This ordering corresponds to a scheduling of the tasks that obeys the precedence constraints. The goal is to minimize the storage-time product. Assuming that all tasks are of unit length, this translates to minimizing the cost of the ordering defined by cost(h) ?? [[Sigma].sub.u [right arrow] v](h(v) - h(u)) [multiplied by] c(u [right arrow] v).

The divide-and-conquer condition is applied in the same manner as it is applied to the undirected linear arrangement problem. The graph H = (V, [E.sub.H]) associated with G = (V, E) is the clique graph [C.sub.|V|], and the scaler function is defined by scaler(H = (V, [E.sub.H])) ?? |V| - 1. Since the graph here is directed we need to modify the way the spreading metric is computed. Following Ravi et al. [1991], we augment the graph by adding reversed edges, [E.sup.R] ?? {v [right arrow] u:u [right arrow] v [element of] E} with infinite capacity. The spreading metrics is defined by the following linear program:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[inverted] Ae [element of] E [union] [E.sup.R]: l(e) [is greater than or equal to] 0

We use the convention that [infinity] [multiplied by] 0 = 0, and hence, infinite capacity edges are assigned zero length.

The required properties of the spreading metric are proved in the following Lemmata which are analogous to Lemma 10 and 11.

LEMMA 15. Let l(e) denote a feasible solution of the linear program. For every subset U [subset or equal to] V (|U| [is greater than] 1), and for every vertex v [element of] U, there is a vertex u [element of] U for which

max{[dist.sub.l](u, v), [dist.sub.l](v, u)} [is greater than or equal to] 1/8 [multiplied by] |U|.

Note that again the bound on the diameter of a subset U is 1/8 [multiplied by] |U|, which is smaller than the value |U| - 1 required by the "diameter guarantee". However, the ratio is at most 8, and hence, this affects only the constant in the approximation factor.

LEMMA 16. The cost of an optimal solution of the linear program is a lower bound on the cost of an optimal linear ordering of G.

PROOF. The proof follows the proof of Lemma 11. Note that since the reversed edges have infinite capacity they must be given zero length in order that the cost would be bounded. Thus, when we follow the lines of Lemma 11 we ignore these edges and consider only the original edges. []

6.5. INTERVAL GRAPH COMPLETION. The interval graph completion problem is defined as follows:

Input: A connected undirected graph G = (V, E).

Output: A minimum cardinality set of edges F such that G = (V, E [union] F) is an interval graph.

We present a novel method for obtaining a lower bound on the optimal interval completion problem that is based on a linear programming formulation. We rely on the characterization of interval graphs due to Ramalingam and Pandu Rangan [1988]. A graph is an interval graph if and only if there exists a linear ordering of the vertices such that if a vertex u with index i has an edge to vertex v with index j, where i [is less than] j, then every vertex whose index is between i and j also has an edge to vertex v. Note that such an ordering of the vertices of G uniquely defines a completion of G into an interval graph. Thus, it suffices to show how to compute such an optimal ordering.

The following lemma uses the above characterization to establish a relation between the difference in indices of pairs of vertices and the sum of vertex degrees along any path connecting them.

LEMMA 17. Let H = (V, E) be an interval graph. Let h: V [right arrow] {1, ..., |V|} be a linear ordering of its vertices with the property guaranteed by the above characterization. Then, for every path P, p = [v.sub.1], [v.sub.2], ..., [v.sub.p] in H,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where deg(v) denotes the degree of vertex v.

PROOF. Without loss of generality, assume that h([v.sub.p]) [is greater than or equal to] h([v.sub.1]). Consider only the set of "right-going" edges in path P, denoted by [P.sub.r]. For each such edge ([v.sub.i], [v.sub.i+1]), h([v.sub.i+1]) [is greater than or equal to] h([v.sub.i]). The above characterization ensures that all vertices between [v.sub.i] and [v.sub.i+1] are connected to [v.sub.i+1]. It follows that deg([v.sub.i+1]) [is greater than or equal to] h([v.sub.i+1]) - h([v.sub.i]). Thus,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

We apply the "vertex version" of the paradigm as follows. Each vertex is assigned a unit capacity. The graph H = (V, [E.sub.H]) associated with G = (V, E) is the clique graph [C.sub.|V|], and the scaler function is defined by scaler(H = (V, [E.sub.H])) = |V| - 1. To establish the divide-and-conquer applicability we consider any binary decomposition tree T that fully decomposes the problem. As before, each leaf of T corresponds to a distinct vertex of G. However, since we deal now with the "vertex version" each internal tree node t [element of] T is associated with a vertex separator [F.sub.t] rather than an edge cut. Namely, let [G.sub.t] be the subgraph of G induced by [V.sub.t], and denote the two children of t by [t.sub.L] and [t.sub.R]. Then, [F.sub.t] is the vertex separator that separates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [G.sub.t]. Clearly, the sets [F.sub.t] for all t [element of] T are disjoint and do not contain any vertex that corresponds to a leaf of T. The vertex ordering which defines a solution to the interval graph completion problem that is represented by T is defined recursively following the nested dissection construction introduced by Ravi et al. [1991]. Consider an internal tree node t [element of] T and denote its two children by [t.sub.L] and [t.sub.R]. The ordering represented by [T.sub.t] is given by the ordering represented by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] , followed by the ordering represented by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] , followed by the vertices in [F.sub.t] in arbitrary order. The cost of the tree r is cost(T) = [[Sigma].sub.t [element of] T](|[V.sub.t]| - 1)|[F.sub.t]|. To show that this cost bounds on the cost of the solution represented by T, we prove that for every tree node t the cost of [T.sub.t] bounds the cost of the solution represented by [T.sub.t]. Again, we prove the claim by induction on the level of the tree nodes. The claim clearly holds for all leaves of T. Consider an internal tree node t [element of] T and denote its two children by [t.sub.L] and [t.sub.R]. By induction the claim holds for both [t.sub.L] and [t.sub.R]. The inductive claim follows since

cost([T.sub.t]) [is less than or equal to] cost([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) + cost([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) + (|Vt| - 1) [multiplied by] |[F.sub.t]|.

The above inequality holds because at most (|[V.sub.t]| - 1) edges need to be added per each vertex in [F.sub.t]. Note that adding these edges is equivalent to making the intervals corresponding to [F.sub.t] intersect all other intervals in [V.sub.t].

The spreading metric is obtained by solving the following linear program. Since we are using a vertex version of the paradigm, we attach a length l(v) to each vertex v, where l(v) can be viewed as a fractional relaxation of the degree of v in an optimal solution. Let [dist.sub.l](u, v) denotes the shortest path connecting u and v with respect to the vertex lengths l(v).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[inverted] Av [element of] V: l(v) [is greater than or equal to] 0

The following two lemmata are analogous to Lemmata 10 and 11 and are proved similarly.

LEMMA 18. Let l(v) denote a feasible solution of the linear program. For every subset U [subset or equal to] V, and for every vertex v [element of] U, there exists a vertex u [element of] U for which [dist.sub.l](u, v) [is greater than or equal to] (1/4)|U|.

LEMMA 19. The cost of an optimal solution of the linear program is a lower bound on the minimum number of edges in an interval graph completion of G.

PROOF. Consider a completion of G to an interval graph G*(V, E*). For every v [element of] V, let l(v) be the degree of v in G*. Clearly, the cost (1/2)[[Sigma].sub.v [element of] V]l(v) equals the number of edges in E*. We show feasibility of this solution by considering a linear ordering h([multiplied by]) of G* with the property guaranteed by the characterization above. Fix a subset U [subset or equal to] V and a vertex v [element of] U. Consider a shortest path P, with respect to l([multiplied by]), that connects v and u, [dist.sub.l](u, v) = [[Sigma].sub.x [element of] P]l(x). Since l(x) is the degree of x in G*, by Lemma 17 we have [[Sigma].sub.x [element of] P]l(x) [is greater than or equal to] |h(u) - h(v)l. Summing over all vertices in U and using Lemma 11, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and the lemma follows. []

6.6. SUBSET FEEDBACK SETS IN DIRECTED GRAPHS AND MULTICUTS IN CIRCULAR NETWORKS. In this subsection, we consider a generalization of the weighted feedback set called the weighted subset feedback set problem. This problem has two versions, subset feedback edge set (SUBSET-FES), and subset feedback vertex set (SUBSET-FVS), which were shown to be equivalent in Evan et al. [1998]. Thus, we consider here only the SUBSET-FES problem defined as follows:

Input: A directed graph G = (V, E) with capacities c(e) associated with each edge e [element of] E. A subset X [subset or equal to] V of "special" vertices, where |X| = k.

Output: A minimum capacity subset of edges that intersects every interesting cycle, that is, a cycle containing a vertex from X.

In Evan et al. [1998], it is shown that this problem is equivalent to the problem of finding a multicut in a circular network which is defined as follows:

Input: A directed graph G = (V, E) with a capacity c(e) associated with every e [element of] E, and a set of k source-sink pairs [{([s.sub.i], [t.sub.i])}.sub.i = 1], ..., k. For every source-sink pair, ([S.sub.i], [t.sub.i]), there is an infinite capacity edge [t.sub.i] [right arrow] [s.sub.i].

Output: A minimum capacity subset of edges F [subset or equal to] E that intersects every path in G from a source to its corresponding sink.

We show how to cast the multicut problem in our paradigm. The directed graph H = (V, [E.sub.H]) associated with G = (V, E) is the "demands" graph, defined by the set of edges [E.sub.H] = [{([s.sub.i], [t.sub.i])}.sub.i = 1], ..., k. The scaler function is defined by scaler(H = (V, [E.sub.H])) = 1 if [E.sub.H] is nonempty, and 0 otherwise. Clearly, if [E.sub.H] = 0, then all the source-sink pairs are separated and the problem (G, H) is trivial. To establish the divide-and-conquer applicability, we consider any binary decomposition tree T that fully decomposes the problem. Consider an internal tree node t [element of] T and denote its two children by [t.sub.L] and [t.sub.R]. Let [F.sub.t] be the (directed) ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) cut in the subgraph induced by [V.sub.t]. (Namely, the edges in [F.sub.t] intersect any path from a vertex from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to a vertex in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].) The solution to the multicut problem that is represented by T is given by the union of all cuts [F.sub.t], for t [Element of] T. Note that this union would not constitute a solution for arbitrary directed multicut problems, but only for circular networks which have infinite capacity edges from each sink to its corresponding source. The reason for this is that a region that is grown by the partition procedure around a terminal (either a source [s.sub.i] or a sink [t.sub.i]), may not contain a sink [t.sub.j] without containing the source [s.sub.j]. Therefore, if an additional source-sink pair [s.sub.j], [t.sub.j] happens to be separated by a region, then the selected directed cut separates this pair in the right direction (i.e., covering every path from [s.sub.j] to [t.sub.j]). The cost of the tree T is cost(T) = [[Sigma].sub.t [element of] T]c([F.sub.t]). To show that this cost bounds, the solution to the multicut problem that is represented by T, we prove that for every tree node t the cost of [T.sub.t] bounds the cost of the solution represented by [T.sub.t]. As before, we prove the claim by induction on the level of the tree nodes. For each leaf, the subgraph induced by the leaf corresponds to a trivial problem. For each internal tree node t, we have

cost([T.sub.t]) [is less than or equal to] cost([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) + cost([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) + c([F.sub.t]).

The inductive claim follows.

The spreading metric is defined by the following linear program:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[inverted] Ae [element of] E: l(e) [is greater than or equal to] 0

The following two lemmata prove that the spreading metric meets the required properties. The next lemma is immediate.

LEMMA 20. Let l(e) denote a feasible solution of the linear program. For every subset U [subset or equal to] V, if U contains a source-sink pair, then the distance from the source to the sink is at least 1.

LEMMA 21. The cost of an optimal solution of the linear program is a lower bound on the cost of an optimal multicut of G.

PROOF. Given a multicut of G, denoted by F, define l(e) to be the indicator function of F. Clearly, l([multiplied by]) is feasible and its cost equals the capacity of F. []

6.7. SYMMETRIC MULTICUTS IN DIRECTED GRAPHS. Klein et al. [1997] considered a variant of network decomposition, called symmetric multicuts:

Input: A directed graph G = (V, E) with a capacity c(e) associated with every l [element of] E, and a set of k terminal pairs [{([s.sub.i], [t.sub.i])}.sub.i = 1], ..., k.

Output: A minimum capacity subset of edges F [subset or equal to] E such that every terminal pair is separated into two different strongly connected components in the graph G' = (V, E - F).

The symmetric multicut problem is cast in our paradigm similarly to the multicut problem in circular networks. The only difference is that the auxiliary graph is undirected, and has edges connecting terminal pairs.

The spreading metric is computed by the following linear program.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[inverted] Ae [element of] E: l(e) [is greater than or equal to] 0

The following two lemmata are similar to Lemmata 20 and 21.

LEMMA 22. Let l(e) denote a feasible solution of the linear program. For every subset U [subset or equal to] V, if U contains a terminal pair ([s.sub.i], [t.sub.i]), then either the distance from [s.sub.i] to [t.sub.i] is at least 1/2, or the distance from [t.sub.i] to [s.sub.i] is at least 1/2.

LEMMA 23. The cost of an optimal solution of the linear program is a lower bound on the cost of an optimal symmetric multicut of G.

6.8. MULTIWAY SEPARATORS AND [Rho]-SEPARATORS IN DIRECTED GRAPHS. We first discuss the directed [Rho]-separator problem. The problem of finding [Rho]-separators in undirected and directed graphs is introduced in Even et al. [1999]. We consider here only directed graphs since the approximation factor given in Even et al. [1999] for undirected graphs is better than the approximation factor described here. However, both cases can be cast into our paradigm. For simplicity, we consider here only the case in which all vertices have unit weights (although edges may have different capacities); the weighted case is described in Even et al. [1999].

For 0 [is less than] [Rho] [is less than or equal to] 1, recall that a [Rho]-separator in a directed graph G = (V, E) is a subset of edges whose removal partitions G into strongly connected components, each of which contains at most [Rho] [multiplied by] n vertices, where n = |V|. The directed [Rho]-separator problem is defined as follows:

Input: A directed graph G = (V, E) with a capacity c(e) associated with every e [Element of] E, and a parameter 0 [is less than] [Rho] [is less than or equal to] 1.

Output: A minimum capacity directed [Rho]-separator.

The performance of the approximation algorithm for this problem differs from the other problems treated in this paper, and is sometimes called a "pseudo-approximation algorithm" or a "bicriteria approximation algorithm". The input contains instead of a single parameter [Rho], 0 [is less than] [Rho] [is less than or equal to] 1, two parameters [Rho] and v, 0 [is less than] v [is less than] [Rho] [is less than or equal to] 1. The algorithm finds a [Rho]-separator, and the cost of the solution is compared with the cost of an optimal v-separator. Hence, we compare the cost of the found solution with the cost of an optimal solution to a more restricted problem. We need the difference between p and v in order to guarantee a diameter, as described in Lemma 24, and the approximation factor depends also on 1/([Rho] - v). To summarize, we find a [Rho]-separator whose capacity is

O([Rho]/[Rho] - v [multiplied by] min{log n log log n, log [Tau] log log [Tau]} [multiplied by] [Tau]),

where [Tau] denotes the cost of an optimal v-separator.

In Even et al. [1999], we relate the [Rho]-separator problem to the problem of partitioning a graph into q roughly equal parts, which is called the q-balanced partitioning problem. Specifically, we show that if every strongly connected component contains at most [Rho] [multiplied by] n vertices, then every maximal grouping of strongly connected components (such that each group still contains at most [Rho] [multiplied by] n vertices) contains less than 2/[Rho] groups. Hence, we can compute a q-balanced partition by finding a 2/q-separator and grouping the resulting components.

The q-balanced partitioning problem was considered by Leighton et al. [1990] and by Simon and Teng [1997]. They proposed applying recursively the approximate separator algorithm in Leighton and Rao [1999] until all strongly connected components are small enough. This approach yields a q-balanced partitioning in which the number of vertices in each part is bounded by 2n/q. The capacity of the separator is O(log n log q [multiplied by] [Tau]'), where [Tau]' denotes the minimum cost of a 1/q-separator. Our algorithm is more flexible since for any fixed [Epsilon] [is greater than] 0 it yields a partitioning in which each part contains at most (1 + [Epsilon])n/q vertices, where the capacity of the separator is O((1/[Epsilon]) [multiplied by] min{log n log log n, log [Tau]' log log [Tau]'} [multiplied by] [Tau]'). If we compare these results for [Epsilon] = 1, then our algorithm is superior to the recursive algorithm when q [is greater than] min{log n, [[Tau]'.sup.log log [Tau]'/log n]}.

We now show how to cast the directed [Rho]-separator problem into our paradigm. First, we need to extend the definition of the auxiliary graph to hypergraphs. The hyperedges of the auxiliary hypergraph H = (V, [E.sub.H]) associated with G = (V, E) are defined as follows: X [subset or equal to] V is a hyperedge if |X| [is greater than] v [multiplied by] n and the subgraph [G.sub.x] of G induced by X is strongly connected. For every subhypergraph [H.sub.U] of the hypergraph H induced by a subset of vertices U, the scaler function is defined by scaler([H.sub.U]) = 1 if [H.sub.U] contains at least one hyperedge, and 0 otherwise.

Clearly, if [H.sub.U] lacks hyperedges, then all the strongly connected components in [G.sub.U] are small, and hence, cost([G.sub.U], [H.sub.U]) = 0. Divide and conquer now applies as in Section 6.5 by removing the edges of the directed cut in each divide step.

We now show that an optimal solution to the following linear program is a spreading metric.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[inverted] Ae [element of] E: l(e) [is greater than or equal to] 0

Note that the constraints for small subsets of vertices (namely, |U| [is less than or equal to] v [multiplied by] n) are trivial and may be omitted. Moreover, constraints for subsets |U| [is less than or equal to] [Rho] [multiplied by] n may be omitted since such subsets need not be partitioned. (This reduces the complexity of solving the linear program in some algorithms [Even et al. 1999].)

LEMMA 24. If U [multiplied by] V satisfies |U| [is greater than] [Rho] [multiplied by] n, then for every vertex v [Element of] U, there exists a vertex u [Element of] U, such that

[dist.sub.l](v, u) + [dist.sub.l](u, v) [is greater than] [Rho] - v/[Rho]

The proof of this lemma is similar to the proof of Lemma 10. Note however, that our relaxation of the diameter guarantee adds a factor of 2[Rho]/([Rho] - v) to the approximation factor. Since we cannot guarantee a diameter of at least ([Rho] - v)/2[Rho] unless there are at least [Rho] [multiplied by] n vertices, we obtain a [Rho]-separator rather than a v-separator.

LEMMA 25. The cost of an optimal solution of the linear program is a lower bound on the cost of an optimal v-separator.

PROOF. Consider an optimal v-separator F [subset or equal to] E. Define l(e) to be the indicator function of F. In order to show that l(e) is a feasible solution of the linear program, consider an arbitrary constraint for U [subset or equal to] V and v [element of] U. Define [comp.sub.F](V) to be the set of vertices in the strongly connected component of G' = (V, E - F) that contains vertex v. Since F is a v-separator, it follows that |[comp.sub.F](V)| [is less than or equal to] v [multiplied by] n. If u [is not an element of] [comp.sub.F](V), then either every path from u to v contains an edge from F, or every path from v to u contains an edge of F. Hence, [dist.sub.l](v, u) + [dist.sub.l](u, v) [is greater than or equal to] 1, and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] []

7. Further Results

Since the preliminary version of this paper appeared in Even et al. [1995], several new applications of spreading metrics were discovered.

(1) Even et al. [1999] used spreading metrics to obtain improved approximation factors for balanced partitioning problems.

(2) Kuo and Cheng [1997] used spreading metrics for partitioning problems that arise in VLSI design.

(3) Rao and Richa [1998] improved the approximation factor for the linear arrangement problem and for the interval graph completion problem to O(log n).

(4) Blum et al. [1998] used spreading constraints in a semi-definite program for approximating the bandwidth problem and obtained an approximation factor of O([square root of n]). It is interesting to note that this is the best approximation factor that can be achieved for this problem using spreading constraints. To obtain polylogarithmic approximation factors, more constraints need to be introduced, as shown by Feige [1998]. Based on Feige's volume preserving embeddings, Vempala [1998] used a spreading metric similar to the spreading metric used in this paper for graph embeddings in d-dimensional meshes to compute edge lengths which are used by the volume preserving embedding. Vempala presented a polylogarithmic approximation algorithm for the bandwidth problem in embeddings in d-dimensional meshes as well as a bicriteria polylogarithmic approximation algorithm that minimizes the bandwidth and the sum of the edge lengths in embeddings in d-dimensional meshes.

(1) Indeed, linear arrangement is a special case of embedding a graph in a d-dimensional mesh. We separate the problems for simplicity of exposition, since solving the more general problem requires extra ideas.

REFERENCES

AUMANN, Y., AND RABANI, Y. 1998. An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27, 291-301.

BAR-YEHUDA, R., EVEN, G., AND NAOR, J. 1998. Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems. Manuscript.

BLUM, A., KONJEVOD, G., RAVI, R., AND VEMPALA, S. 1998. Semi-definite relaxations for minimum bandwidth and other vertex ordering problems. In Proceedings of the 30th ACM Symposium on Theory of Computing. ACM, New York, pp. 100-105.

BHATT, S. N., AND LEIGHTON, F.T. 1984. A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28, 300-343.

EVEN, G., NAOR, J., RAO, S., AND SCHIEBER, B. 1998. Divide-and-conquer approximation algorithms via spreading metrics. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science. IEEE Computer Science Press, Los Alamitos, Calif., pp. 62-71.

EVEN, G., NAOR, J., RAO, S., AND SCHIEBER, B. 1999. Fast approximate graph partitioning algorithms. SIAM J. Comput. 28, 6, 2187-2214.

EVEN, G., NAOR, J., SCHIEBER, B., AND SUDAN, M. 1998. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20, 151-174.

FEIGE, U. 1998. Approximating the bandwidth via volume respecting embeddings. In Proceedings of the 30th ACM Symposium on Theory of Computing. ACM, New York, pp. 90-99.

GAREY, M. R., AND JOHNSON, D.S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, Calif.

GROTSCHEL, M., LOVASZ, L., AND SCHRIJVER, A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York.

GARG, N., VAZIRANI, V. V., AND YANNAKAKIS, M. 1996. Approximate max-flow min-(multi) cut theorems and their applications. SIAM J. Comput. 25, 235-251.

HANSEN, M. 1989. Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 604-609.

KUO, M.-T., AND CHENG, C.-K. 1997. A network flow approach for hierarchical tree partitioning. In Proceedings of the 34th ACM-IEEE Design Automation Conference (Anaheim, Calif., June 9-11). ACM, New York, pp. 512-517.

KLEIN, P. N., PLOTKIN, S. A., RAO, S., AND TARDOS, E. 1997. Approximation algorithms for Steiner and directed multicuts. J. Algorithms 22, 241-269.

LEIGHTON, F. T., MAKEDON, F., AND TRAGOUDAS, S. 1990. Approximation algorithms for VLSI partition problems. In Proceedings of the IEEE International Symposium on Circuits and Systems. IEEE Computer Society Press, Los Alamitos, Calif. pp. 2866-2868.

LEIGHTON, F. T., AND RAO, S. 1999. An approximate max-flow rain-cut theorem for uniform multi-commodity flow problems with applications to approximation algorithms. J. ACM, 46, 6 (Nov.), 787-832.

LINIAL, N., LONDON, E., AND RABINOVICH, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 215-245.

NESTEROV, Y., AND NEMIROVSKII, A. 1994. Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia.

RAVI, R., AGRAWAL, A., AND KLEIN, P. 1991. Ordering problems approximated: Single processor scheduling and interval graph completion. In Proceedings of the 18th International Colloquium on Automata, Languages and Programming. pp. 751-762.

RAMALINGAM, G., AND PANDU RANGAN, C. 1988. A unified approach to domination problems in interval graphs. Inf. Proc. Lett. 27, 271-274.

RAO, S., AND RICHA, A. 1998. New approximation techniques for some ordering problems. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 211-219.

SAGAN, H. 1994. Space-Filling Curves. Springer-Verlag, New York.

SEYMOUR, P.D. 1995. Packing directed circuits fractionally. Combinatorica 15, 281-288.

SHMOYS, D.B. 1997. Cut problems and their application to divide-and-conquer. In Approximation algorithms for NP-hard problems. D. S. Hochbaum, Ed. PWS Publishing Co.

SIMON, H. D., AND TENG, S-H. 1997. How good is recursive bisection. SIAM J. Sci. Comput. 18, pp. 1436-1445.

VEMPALA, S. 1998. Random projection: A new approach to VLSI layout. In Proceedings of the 39th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 389-395.

RECEIVED FEBRUARY 1996; REVISED SEPTEMBER 1999; ACCEPTED SEPTEMBER 1999

A preliminary version of this paper appeared in the Proceedings of the 36th Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 1995, pp. 62-71.

The research of J. Naor was supported in part by Grant No. 92-00225 from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel. His research was also supported by the Fund for the Promotion of Research at the Technion.

This work was done while S. Rao was with NEC Research Institute, 4 Independence Way, Princeton, NJ 08540.

Authors' present addresses: G. Even, Department of Electrical Engineering, Tel-Aviv University, Tel-Aviv 69978, Israel, e-mail: guy@eng.tau.ac.il; J. Naor, Computer Science Dept., Technion, Haifa 32000, Israel, e-mail: naor@cs.technion.ac.il; S. Rao, University of California, Computer Science Division, Soda Hall, Berkeley, CA 94720-1776, e-mail: satish@cs.berkeley.edu; B. Schieber, IBM T. J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY 10598, e-mail: sbar@watson. ibm.com.

Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery (ACM), Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.

[C] 2000 ACM 0004-5411/00/0700-0681 $05.00

Printer friendly Cite/link Email Feedback | |

Author: | EVEN, GUY; NAOR, JOSEPH; RAO, SATISH; SCHIEBER, BARUCH |
---|---|

Publication: | Journal of the Association for Computing Machinery |

Geographic Code: | 1USA |

Date: | Jul 1, 2000 |

Words: | 16676 |

Previous Article: | Noise-Tolerant Distribution-Free Learning of General Geometric Concepts. |

Next Article: | Speed Is as Powerful as Clairvoyance. |

Topics: |