Approximating layout problems on random sparse graphs

Approximating Layout Problems on Random Sparse Graphs∗ J. D´ıaz †J. Petit†M. Serna†L. Trevisan‡ March 7, 2001 Abstract We show that, with high probability, several layout problems are approximable within a constant for random graphs drawn from the standard Gn,p model with p=c/n for some constant c. Our results establish that, in fact, any algorithm that returns a feasible solution will produce such an approximation for graphs with good expansion properties. 1 Introduction Linear arrangement problems play an important role in Computer Science [27, 1, 8]. A linear layout (or linear arrangement or vertex ordering) of a graph Gwith nnodes is a one-to-one mapping of the vertices of Gto the set {1,...,n}. A layout πon G= (V, E) determines in a unique way a nested sequence of vertex subsets containing those vertices placed up to the i-th position. The layout also induces an assignment of lengths to every edge in the graph: the length induced by a layout πfor an edge e=uv ∈Eis λ(π, e) = |π(u)−π(v)|. The complexity of a graph in terms of a linear layout is usually obtained by measuring length, crossing edges or neighbors placement. The bandwidth problem asks for a layout minimizing the maximum edge length. The problem is NP-complete [28], even for trees with maximum degree 3 [14] or caterpillars with hair length 3 [25]. It can be approximated within a constant for some restricted classes of trees [18], but has no polynomial time approximation scheme for trees [4]. It has a constant randomized approximation algorithm for dense instances [21], and no polynomial time approximation algorithm for general graphs [20]. The minimum cut arrangement asks for a layout minimizing the maximum cut along the nested sequence of vertex sets. The problem is NP-complete [17], even for planar graphs with maximum degree 3 [26]. For trees the problem is in P[33] and even in NC [9]. It can be approximated within any constant for dense graphs [3]. A variation ∗This research was supported by the ESPRIT Long Term Research Project No. 20244, ALCOM-IT (WP 3.3) and CICYT project TIC97-1475-CE. The first and third authors were also supported by CIRIT project 1997SGR-00366. †Departament de Llenguatges i Sistemes Inform`atics, Universitat Polit`ecnica Catalunya, Campus Nord C6, Jordi Girona Salgado 1-3, 08034 Barcelona, Spain. {diaz,jpetit,mjserna}@lsi.upc.es ‡MIT Laboratory for Computer Science Room NE43-371, 545 Technology Square, Cambridge MA 02139-3594, USA. [email protected] 1 of the problem in which the cut excludes edges touching the last vertex is known as the minimum modified cut arrangement and is also NP-complete for planar graphs with maximum degree 3 [26]. The minimum linear arrangement problem (also known as the minimum edge sum [19] or the optimal linear ordering [1]) seeks a layout that minimizes the total edge length. This problem is also NP-complete [16]. For trees the problem is in P[31] and in NC [9]. It can be approximated within a O(log2n) factor using the approximate max flow-min cut theorem [23]. A better approximation factor O(log nlog log n) can be achieved using spreading metrics [13]. This result has been improved recently to a O(log n) approximation for general graphs and to a O(log log n) factor for planar graphs [30]. On the other hand, the problem can be approximated within a 1+ǫfactor in time nO(1/ǫ)when restricted to dense graphs using linear programming and random rounding [3]. Nothing is known about the hardness of approximating the minimum linear arrangement problem, which is not even known to be max-SNP-hard. In [29] some heuristics algorithms to approximate this problem are empirically studied. The maximum linear arrangement problem that asks for a layout maximizing the total edge length is not of practical interest, but it is worth noting that its approximability properties are entirely understood: A greedy algorithm can be used to obtain an approximation within a factor of 2 [11]. The vertex separation problem has the same formulation as the minimum cut arrangement problem, but using as measure the number of vertices in the first partition connected to the second one. This measure was first introduced in [7] as the δ-operator. The problem is NP-complete [24], but in Pfor trees [12]. The global version in which one looks for a layout minimizing the sum of all the separations is known as the minimal sum cut problem [10] or the minimal profile problem [22]. The problem is equivalent to the interval graph completion problem that is also NP-complete [15]. For trees the problem is in P[22] and in NC [10]. An approximation factor O(log nlog log n) can be obtained using spreading metrics [13]. The above results establish the difficulty in dealing with sparse graphs. In general, considering only dense instances makes a problem easier because such graphs inherit most of the good properties of dense random graphs. In this paper we try to analyze the difficulty of approximating some of the above problems for random sparse graphs (drawn from the standard Gn,p model with p=c/n [5, 2]) and expanders. A natural question is to ask whether there is any relation between the approximability of the maximization version of the problems, and whether we can infer some consequence for the minimization version from our understanding of these maximization versions. It thus makes sense to introduce the gap between the maximum an the minimum values, the ratio between the maximum and the minimum values, and to estimate this gap value for interesting classes of graphs. Note that whenever we can bound the gap for a certain constant r>1, it follows that any arrangement of Gis r-approximate for both the minimization and maximization problems. For instance, in the case of the minimum linear arrangement problem, it is clear that the gap is 1 for any complete graph G. Moreover, for a graph that has only one edge, the gap is n(and this is the largest possible gap). Those extremal cases suggest that the gap for this problem is related to the connectivity property of a graph, and thus it seems unlikely that we can find a bounded degree graph with a small gap value, and one would thing that, at least, almost all (in the probabilistic sense) sparse graphs have a large gap value. We will show that the opposite results hold. 2 2 Definitions and basic results Consider an undirected graph G= (V, E) with n=|V|vertices and m=|E|edges. We denote by N(u) the set of neighbors of a vertex uincluding u. A layout for Gis any bijective function that associates to each vertex a number in the range {1,... ,n}= [n]. Given a layout πfor G, for any i∈[n] consider the sets L(i) = {v|π(v)≤i}and R(i) = {v|π(v)> i}. For a given layout π, define λ(e, π) = |π(u)−π(v)|e=uv ∈E cut(i, π) = |{uv ∈E|u∈L(i)∧v∈R(i)}| i∈[n] mod-cut(i, π) = |{uv ∈E|u∈L(i)− {i} ∧ v∈R(i)}| i∈[n] δ(i, π) = |{u∈L(i)| ∃w∈R(i) : (u, w)∈E}| i∈[n] Definition 1. The formal definitions of the problems we study are the following: •Minimum linear arrangement (minla). Given a graph G= (V, E), find a layout π that minimizes la(G, π) = n−1 X i=1 cut(i, π) = X e∈E λ(e, π). •Minimum sum modified cut (minmla). Given a graph G= (V, E), find a layout π that maximizes mla(G, π) = n−1 X i=1 mod-cut(i, π). •Minimum sum cut (minsc). Given a graph G= (V, E), find a layout πthat minimizes sc(G, π) = n−1 X i=1 δ(i, π). We will also consider the maximization versions of such problems, namely the maximum linear arrangement (maxla), the maximum sum modified cut (maxmla), and the maximum sum cut (maxsc). For sake of simplicity, for a given measure F, we will use the notations maxF(G) = max πF(G, π) minF(G) = min πF(G, π) avF(G) = PπF(G, π) n! to denote its maximum, minimum and average values. Definition 2. For a measure F, we define the gap between the minimum and maximum values as gapF(G) = maxF(G) minF(G)= 1 + maxF(G)−minF(G) minF(G). 3 Definition 3. Given a constant r, an algorithm Ais an r-approximation to a minimization (maximization) problem for a function Fwhen it holds that for any graph G A(G) minF(G)≤1 + rmaxF(G) A(G)≤1 + r. Equivalently, the value ǫ= 1 −ris called the approximation ratio of the r-approximate algorithm A[15]. Observe that any bound on the second expression in our definition gives a bound on the approximation ratio of any algorithm that computes a layout for G. Basic results. Given a graph G= (V, E) with nnodes and medges, it is well known that the average length of an edge e=uv is (n+1)/3. Taking into account that la(G, π) is the sum of all edge lengths we have avla(G)≥m(n+1)/3. To bound the average modified cut cost we use the following straightforward relationship: mla(G, π)+Pv∈Vd(v)≥la(G, π). The same relationship holds for the average value and we have that avmla(G)≥m(n− 5)/3. To analyze the average sum cut cost we consider a simplified measure. Given a graph G= (V, E) each vertex uselects a neighbor s(u)6=uif any, for an isolated vertex set s(u) = u. We will use an arbritary (but fixed) selection s. Given a layout πdefine D(G, π) = Pv∈Vmax(0, π(v)−π(s(v))). Notice that for all π,sc(G, π)≥D(G, π). Furthermore the expected contribution of the edge (v, s(v)) is 0 with probability 1/2 and (n+ 1)/3 with probability 1/2, that is (n+ 1)/6. Adding up for all vertices we get avsc(G)≥n(n+ 1)/6. 3 The graphs We introduce now two graph classes that capture the properties needed to bound the gap. Definition 4 (Mixing graphs). Let 0 < γ, ǫ < 1 and c > 0. A graph G= (V, E) with |V|=nand |E|=mis said to be (ǫ, γ, c)-mixing if for any two disjoint sets A, B ⊆V such that |A| ≥ ǫn,|B| ≥ ǫn, it is the case that θ(A, B)−c n· |A||B|≤γc n· |A||B|, where θ(A, B) is the number of edges of Ghaving one endpoint in Aand another in B. Definition 5 (Disperser graphs). Let 0 < ǫ < 1. A graph G= (V, E) with |V|=n and |E|=mis said to be an ǫ-disperser if for any two disjoint sets A, B ⊆Vsuch that |A| ≥ ǫn, and |B| ≥ ǫn there is at least an edge having an endpoint in Aand an endpoint in B. It is known that explicit constructions of expander graphs imply efficient construction of mixing graphs. In particular, the following result holds. Theorem 1 (See e.g. [6]). A constant αexists such that for any ǫ, γ > 0, for any n and any d≥α/(ǫ2γ2), an (ǫ, γ, m/n)-mixing graph with maximum degree at most dcan be constructed in poly(n)time. Remark that from the definition of mixing and disperser graphs, it follows that, any (ǫ, γ, c)-mixing graph is also an ǫ-disperser, and so Theorem 1 also gives an explicit construction of disperser graphs. 4 Theorem 2. A constant βexists such that for any ǫ > 0, for any nand any d≥β/ǫ2, an ǫ-disperser graph with nvertices and maximum degree at most dcan be constructed in poly(n)time. Definition 6 (Random sparse graphs [5, 2]). We consider the standard class of random graphs Gn,p which have nnodes and each potential edge exists with probability p. Although the random sparse graphs considered in this paper are expected to be non connected, with high probability they have good mixing properties. Lemma 1 (Chernoff bounds). Let X1,... ,Xnbe independent random variables whose range is {0,1}. Let µ=E[Pn i=1 Xi]. Then for any 0< γ < 1it is the case that Pr "(1 −γ)µ≤ n X i=1 Xi≤(1 + γ)µ#≥1−2 exp(−γ2µ/3). Theorem 3 (Random graphs are mixing). For any ǫ, γ > 0, for any c≥3.296 ǫ2γ2, random graphs drawn from Gn,p with p=c/n are (ǫ, γ, c)-mixing with probability at least 1−2−Ω(n). Proof. Consider any two sets A, B ⊆Vsuch that |A|,|B| ≥ ǫn. There are k=|A||B| possible edges having an endpoint in Aand an endpoint in B. Let us call Y1,... ,Ykthe random variables such that Yi= 1 if the i-th (in lexicographical order) of such edges is in the graph, and Yi= 0 otherwise. The average of Pk i=1 Yiis clearly µ=c|A||B|/n. Then we have that Pr "(1 −γ)µ≤ k X i=1 Yi≤(1 + γ)µ#≥1−exp(γ2µ 3+ 1). Since there are at most 3nchoices for the sets Aand B, it follows that the probability that the graph is not mixing is at most exp (ln 3)n−γ2c|A| |B| n 1 3−1. Note that the term in the exponent is nln 3 −cγ2ǫ21 3−1/n≤ −Ω(n). As mixing graphs are dispersers, we also have that random graphs are disperser graphs with high probability. 4 Bounding the Gap Now we bound the gap between the maximum and minimum costs for mixing graphs. 5 Lemma 2. Let G= (V, E)be an (ǫ, γ, c)-mixing graph (with 0<ǫ, γ <1), then gapla(G)≤1 + 1 1−γ6ǫ 1−6ǫ(1 + γ) + 2γ= 1 + O(ǫ+γ). Proof. Let πbe any layout of G. We will bound its cost from above and from below: la(G, π) = n−1 X i=1 cut(i, π)≥ n−ǫn X i=ǫn cut(i, π)≥(1 −γ)c n n−ǫn X i=ǫn i(n−i). For the lower bound, la(G, π) = n−1 X i=1 cut(i, π)≤2ǫmn + n−ǫn X i=ǫn cut(i, π)≤2ǫmn + (1 + γ)c n n−ǫn X i=ǫn i(n−i). Therefore, letting S=c nPn−ǫn i=ǫn i(n−i), we have maxla(G)≤2ǫmn + (1 + γ)S, minla(G)≥(1 −γ)S, maxla(G)−minla(G)≤2ǫmn + 2γS. As avla ≥m(n+ 1)/3 there is a layout that gives at least this value so, 2ǫmn + (1 + γ)S≥m(n+ 1) 3>mn 3 therefore 2ǫmn ≤6ǫ 1−6ǫ(1 + γ)Sand we get gapla(G)≤1 + 6ǫ 1−6ǫ(1 + γ)S+ 2γS (1 −γ)S. A similar result holds for the minimum sum modified cut problem. Lemma 3. Let G= (V, E)be an (ǫ, γ, c)-mixing graph (with 0< ǫ, γ < 1) with |V|>9. Then gapmla(G)≤1 + 1 1−γ12ǫ 1−12ǫ(1 + γ) + 2γ= 1 + O(ǫ+γ). Proof. Let πbe any arrangement. We will bound its cost from above and from below: mla(G, π) = n−1 X i=1 mod-cut(i, π)≥ n−ǫn−1 X i=ǫn+1 mod-cut(i, π)≥(1 −γ)c m n−ǫn−1 X i=ǫn+1 (i−1)(n−i). For the lower bound, mla(G, π) = n−1 X i=1 cut(i, π)≤2(ǫn + 1)m+ n−ǫn−1 X i=ǫn+1 mod-cut(i, π) ≤2ǫnm + (1 + γ)c n n−ǫn−1 X i=ǫn+1 (i−1)(n−i) 6 where the last inequality holds because mod-cut(1, π) = mod-cut(n, π) = 0 for any layout π. Therefore, letting T=c nPn−ǫn−1 i=ǫn+1 (i−1)(n−i), we have maxmla(G)≤2ǫnm + (1 + γ)T, minmla(G)≥(1 −γ)T, maxmla(G)−minmla(G, π)≤2ǫnm + 2γT. As avmla =m(n−5)/3 there is a layout that gives at least this value so, 2ǫnm + (1 + γ)T≥m(n−5) 3 and as n > 9 it holds that n−5≥n/2. Therefore 2ǫnm + (1 + γ)T≥mn 6and we get 2ǫnm ≤12ǫ 1−12ǫ(1 + γ)T. A similar results holds for the minimum sum cut problem. Lemma 4. Let G= (V, E)be an ǫ-disperser graph (with ǫ < 1), then gapsc(G)≤1 1−4ǫ. Proof. We find lower and upper bounds for the value sc(G). We first notice that in an ǫ-disperser graph it is the case that δ(π, i)≥i−ǫn for every ǫn < i < n −ǫn. This is because there cannot be ǫn vertices on the left of iand ǫn vertices on the right of iwithout any connection. sc(G, π) = n−1 X i=1 δ(π, i)≥ n−ǫn X i=ǫn δ(π, i)≥ n−ǫn X i=1 (i−ǫn) >(n−ǫn)2/2−ǫn(n−ǫn)> n2/2−2ǫn2. For the upper bound, we get sc(G, π) = n−1 X i=1 δ(π, i)≤ n−1 X i=1 i= (n−1)n/2≤n2/2. Thus, we have minsc(G)≥n2/2−2ǫn2and maxsc(G)≤n2/2 and thus gapsc ≤1 1−4ǫ. Consequently, we have established the following theorem: Theorem 4. The problems minla and minmla can be approximated within a constant on mixing graphs. The minsc problem can be approximated within a constant on disperser graphs. Furthermore, there exists a constant csuch that for any α > 0, for any n, Pr[gapF(G)>1 + α]≤2−n where Gis a random graph from the Gn,p model with p=c α4n, and Fis any of the three measures la,mla,sc. 7 5 Conclusions Similar results can be achieved for the local problems such as bandwidth, mincut layout and vertex separation. For the bandwidth problem fixing any layout and taking the sets formed by the first ǫn vertices and the last ǫn vertices, in an (ǫ, γ, c)-mixing graph we have at least one edge connecting both partitions, and therefore a lower bound for the layout bandwidth of (1 −2ǫ)n. In the case that ǫ < 1/3 we have a 3 approximation. A similar result for the bandwidth minimization is given in [32]. In an (ǫ, γ, c)-mixing graph we have at least (1 −γ)cn/4 edges in the central cut. This is a lower bound for the problem mincut. The bound also applies to the bisection problem, because the central cut splits the graph into two equal sized sets. It also applies to the max cut problem. Therefore we can approximate those problems within a constant, for such graphs. In an (ǫ)-disperser mixing graph we have at least (1/2−ǫ)nnodes in the central cut. So, for nlarge enough we get a constant approximation for the vertex separation problem. It is worth to remark that the obtained results give the approximation regardless the connectivity of the graph. For this class of graphs, to get a constant approximation, it is not necessary to finish off a connected component before starting a new one. A standard way of evaluating the real efficiency (from a practical point of view) of an algorithm is to evaluate its performance on random instances. Our results show that any algorithm computing a layout, no matter how bad (or good), will perform very well on random sparse graphs, pointing out that such evaluations may be unworthy for some problems. References [1] D. Adolphson and T. C. Hu. Optimal linear ordering. SIAM J. on Applied Mathematics, 25(3):403–423, November 1973. [2] N. Alon and J.H. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., New York, 1992. With an appendix by P. Erd˝os, A Wiley-Interscience Publication. [3] S. Arora, A. Frieze, and H. Kaplan. A new rounding procedure for the assignment problem with applications to dense graphs arrangements. In 37th IEEE Symposium on Foundations of Computer Science, 1996. [4] G. Blache, M. Karpinski, and J. Wirtgen. On approximation intractability of the bandwidth problem. Technical Report TR98-014, Electronic Colloquium on Computational Complexity, 1998. [5] B. Bollob´as. Random graphs. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1985. [6] P. Crescenzi, R. Silvestri, and L. Trevisan. To weight or not to weight: Where is the question? In 4th IEEE Israel Symposium on Theory of Computing and Systems, pages 68–77, 1996. 8 [7] J. D´ıaz. The δ-operator. In L. Budach, editor, Fundamentals of Computation Theory, pages 105–111. Akademie-Verlag, 1979. [8] J. D´ıaz. Graph layout problems. In I. M. Havel and V. Koubek, editors, Mathematical Foundations of Computer Science, volume 629, pages 14–24. Springer-Verlag, Lecture Notes in Computer Science, 1992. [9] J. D´ıaz, A. Gibbons, G. Pantziou, M. Serna, P. Spirakis, and J. Tor´an. Parallel algorithms for the minimum cut and the minimum length tree layout problems. Theoretical Computer Science, (181):267–287, 1997. [10] J. D´ıaz, A. M. Gibbons, M. S. Paterson, and J. Tor´an. The minsumcut problem. In F. Dehen, R. J. Sack, and N. Santoro, editors, Algorithms and Datastructure, volume 519, pages 65–79. Lecture Notes in Computer Science, 1991. [11] J. D´ıaz, M. J. Serna, and P. Spirakis. Some remarks on the approximability of graph layout problems. Technical Report LSI 94-16-R, Universitat Polit`ecnica de Catalunya, 1994. [12] J. Ellis, I. H. Sudborough, and J. Turner. The vertex separation and search number of a graph. Information and Computation, (113):50–79, 1979. [13] G. Even, J. Naor, S. Rao, and B. Schieber. Divide and conquer approximation algorithms via spreading metrics. In 36th IEEE Symposium on Foundations of Computer Science, pages 62–71, 1995. [14] M. R. Garey, R. L. Graham, D. S. Johnson, and D. Knuth. Complexity results for bandwidth minimization. SIAM J on Applied Mathematics, 34:477–495, September 1978. [15] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979. [16] M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1:237–267, 1976. [17] F. Gavril. Some NP-complete problems on graphs. In Proc. 11th. Conf. on Information Sciences and Systems, pages 91–95, John Hopkins Univ., Baltimore, 1977. [18] J. Haralambides and F. Makedon. Approximation algorithms for the bandwidth minimization problem for a large class of trees. Theory of Computing Systems, (30):67–90, 1997. [19] L. H. Harper. Optimal numberings and isoperimetric problems on graphs. Journal of Combinatorial Theory, 1(3):385–393, 1966. [20] M. Karpinski and J. Wirtgen. On approximation hardness of the bandwidth problem. Technical Report TR97-041, Electronic Colloquium on Computational Complexity, 1997. [21] M. Karpinski, J. Wirtgen, and A. Zelikovsky. An approximating algorithm for the bandwidth problem on dense graphs. Technical Report TR 97-017, ECCC, 1997. 9