1 A Max-Flow Min-Cut Theorem with Applications in Small Worlds and Dual Radio Networks Rui A. Costa Joa˜o Barros 9 0 0 2 n Abstract a J 0 Intrigued by the capacity of random networks, we start by proving a max-flow min-cut theorem 3 that is applicable to any random graph obeying a suitably defined independence-in-cut property. We ] T then show that this property is satisfied by relevant classes, including small world topologies, which I . are pervasive in both man-made and natural networks, and wireless networks of dual devices, which s c exploit multiple radio interfaces to enhance the connectivity of the network. In both cases, we are able [ to apply our theorem and derive max-flow min-cut bounds for network information flow. 2 v 9 7 Index Terms 3 1 . random graphs, capacity, small world networks, wireless networks 9 0 8 0 I. INTRODUCTION : v i Inthequestforthefundamentallimitsofcommunicationnetworks,whosetopologyistypically X r described by graphs, the connection between the maximum information flow and the minimum a cut of the network plays a singular and prominent role. In the case where the network has one or more independent sources of information but only one sink, it is known that the transmitted information behaves like water in pipes and the capacity can be obtained by classical network Rui A. Costaiswiththe Institutode Telecomunicac¸∼oes and theDepartamento de Cieˆnciados Computadores da Faculdade deCieˆnciasdaUniversidadedoPorto,Porto,Portugal;URL:http://www.dcc.fc.up.pt/∼ruicosta/.Joa˜oBarrosis withtheInstitutodeTelecomunicac¸∼oesand theDepartamento deEngenharia Electrote´cnicaedeComputadores daFaculdade de Engenharia da Universidade do Porto, Porto, Portugal; URL: http://paginas.fe.up.pt/∼jbarros/. This work was supported by theFundac¸a˜o para aCieˆnciae Tecnologia (Portuguese Foundation for Science and Technology) under grants SFRH-BD-27273-2006 andPOSC/EIA/62199/2004. Partsofthisworkhavebeenpresented atITW2006 [1],NetCod2006[2], and SpaSWiN 2007 [3]. January30,2009 DRAFT flow methods. Specifically, the capacity of this network will then follow from the well-known Ford-Fulkerson max-flow min-cut theorem [4], which asserts that the maximal amount of a flow (provided by the network) is equal to the capacity of a minimal cut, i.e. a nontrivial partition of the graph node set V into two parts such that the sum of the capacities of the edges connecting the two parts (the cut capacity) is minimum. Provided there is only a single sink, routing offers an optimal solution for transporting messages both when they are statistically independent [5] and when they are generated by correlated sources [6]. Max-flow min-cut arguments are useful also in the case of multicast networks, in which a single source broadcasts a number of messages to a set of sinks. This network capacity problem was solved in [7], where it is shown that applying coding operations at intermediate nodes (i.e. network coding) is necessary to achieve the max-flow/min-cut bound of a general network. A converseproof forthis problem,knownas thenetworkinformationflow problem,was provided by [8], whereas linear network codes were proposed and discussed in [9] and [10]. When the topology of the network is modeled by a randomly constructed graph, the natural goal is a probabilistic characterization of the minimum cut, which in the spirit of the network information flow literature [7] we shall sometimes call (admittedlywith someabuse) thecapacity of the random network. Although some capacity results of this flavor are available for particular instances, most notably for Erdo¨s-Re´nyi graphs and random geometric graphs [11], the problem remains open for many relevant classes of random graphs. Motivated by this observation, we make the following contributions: A Max-flow Min-cut Theorem: We introduce the independence-in-cut property, which is • satisfied by large classes of random graphs, and derive inner and outer bounds for the minimum cut of any network that possesses this basic property. In contrast with [11], our approach is based on Hoeffding’s inequality, which allows us to prove a theorem that is valid for a larger class of networks. Capacity Bounds for Small-World Networks: Based on the aforementioned max-flow min- • cut theorem, we are able to characterize the max-flow min-cut capacity of Small-World networks with shortcuts and with rewiring [12]. Our results show, somewhat surprisingly, that, up to a constant factor, a rewiring rule that preserves the independence-in-cut property does not affect the capacity of large small-world networks. Capacity Bounds for Dual Radio Networks: We are able to apply our theorem also to • 2 wireless network models in which some of the nodes are able to establish both short-range and long-range connections by means of dual radio interfaces. The capacity bounds thus obtained shed some light on the potential gains of this technology. Our motivation to consider small-world networks, i.e. graphs with high clustering coefficients and small average path length, stems from their proven ability to capture fundamental properties of relevant phenomena and structures in sociology, biology, statistical physics and man-made networks. Beyond well-known examples such as Milgram’s ”six degrees of separation” [13] between any two people in the United States and the Hollywood graph with links between actors, small-world structures appear in such diversenetworks as the U.S. electric power grid, the nervous system of the nematode worm Caenorhabditis elegans [14], food webs [15], telephone call graphs [16], and, most strikingly, the World Wide Web [17]. The term small-world graph itselfwas coined by Wattsand Strogatz, whoin theirseminalpaper [12]defined aclass ofmodels which interpolate between regular lattices and random Erdo¨s-Re´nyi graphs by adding shortcuts or rewiring edges with a certain probability p (see Figures 1 and 2). The most striking feature of thesemodelsisthatforincreasing valuesofp theaverageshortest-pathlengthdiminishessharply, whereas the clustering coefficient, defined as the expected value of the number of links between the neighbors of a node divided by the total number of links that could exist between them, remains practically constant during this transition. Since small-world graphs were first proposed as models for complex networks [12] and [18], most contributions have focused essentially on connectivity parameters such as the degree distribution, the clustering coefficient or the shortest path length between two nodes (see e.g. [19]). In spite of its arguable relevance — particularly where communication networks are concerned — the capacity of small-world networks has, to the best of our knowledge, not yet been studied in depth by the scientific community. The second class of networks addressed in this paper is motivated by the fact that wireless interfaces become standard commodities and communication devices with multiple radio in- terfaces appear in various products. Thus, it is only natural to ask whether the aforementioned devicescanleadtosubstantialperformancegainsinwirelesscommunicationnetworks.Promising examples include [20], where multiple radios are used to provide better performance and greater functionality for users, and [21], where it is shown that using radio hierarchies can reduce power consumption. This growing interest in wireless systems with multiple radios (for example, a Bluetooth interface and an IEEE 802.11 wi-fi card) motivates us to study the impact of dual 3 radio devices on the capacity of wireless networks. The rest of the paper is organized as follows. Section II states the problem and proves our main theorem. The results for small-world networks and dual radio networks then follow in Section III and Section IV, respectively. The paper concludes with Section V. II. MAIN RESULT Consider a graph G = (V,E), where V represents the set of nodes of the graph and E the set of edges connecting these nodes. In the rest of the paper, we assume that the edges in the graph represent communication links with unitary capacity. Definition 1: Consider a graph G = (V,E) with V = n, a source s, a set T of terminals | | and a set R of relay nodes such that V = s R T. Let t be a terminal node, i.e. t T { } ∪ ∪ ∈ and let N be the number of relay nodes, i.e. N = R = n 1 T . A s-t-cut of size x in the | | − −| | graph G is a partition of the set of relay nodes R into two sets V and V such that V = x k k k | | and V = N x, R = V V and V V = . The edges crossing the cut are given by k x x x x | | − ∪ ∩ ∅ E (s,i) : i V , E (j,t) : j V , and E (j,i) : j V ,i V . x x x x ∩{ ∈ } ∩{ ∈ } ∩{ ∈ ∈ } The following definition describes the capacity of a cut as the sum of the capacities of the edges crossing the cut. Definition 2: Consider a graph G = (V,E) and a s-t-cut of size x, with the corresponding sets V and V . The capacity of the cut, denoted by C , is given by C = C + C + x x x x si ji i∈Vx j∈Vxi∈Vx C , where C denotes the capacity of the link between nodes i anPd j. P P jt ij j∈Vx PIn the spirit of [4], we will refer to the value of the minimum s-t-cut as the s-t-capacity, denoted by C . In the case of multiple terminals, denoting by T the set of terminals, the s;t s-T-capacity, denoted by C , is the minimum of the s-t-capacities over all terminals, i.e. s;T C = min C . s;T t∈T s;t Definition 3: We say that a graph G has the independence-in-cut property if, for every cut in the graph C = C + C + C , we have (C = c ) = (C = x si ji jt P x x i∈VxP si i∈Vx j∈Vxi∈Vx j∈Vx c ) P(C = cP) P (CP = c ), i.e. all the variables Qin the sum are si · j∈Vx i∈Vx P ji ji · j∈VxP jt jt independent random variables. Q Q Q Notice that, based on this definition, a graph with the independence-in-cut property is not necessarily a graph in which all the edges in the graph are independent random variables. An example of this is the case of Dual Radio Networks, discussed in detail in Section IV, where we 4 shall show that, although there is dependency between some edges, we have that, given a cut, all the edges crossing it are independent random variables. This observation is valid for every cut. In our approach, we make use of the independence-in-cut property to compute bounds on the probability that the capacity of a cut is close to its expected value. In fact, we shall view a cut as the sum of random variables. Given the independence-in-cut property, these variables are independent, which allows us to provide the desired bounds. If these variables are not independent, i.e. if the edges that cross a given cut are not independent random variables, the computation of these bounds becomes extremely difficult, since we are required to bound the sum of correlated random variables, irrespective of the correlation structure. Capacity bounds for Erdo¨s-Re´nyi graphs and random geometric graphs are the main focus of [11]. The bounds were derived specifically for each of the models, using Chernoff techniques. This limits the analysis to the case of networks with independent and identically distributed edges. We shall use some of the techniques presented in [11], but instead of Chernoff bounds our approach exploits Hoeffding’s inequality [22] to derive a more general result. The resulting theorem is true for any network that verifies the independence-in-cut property — edges are not required to be identically distributed. Our main result is given by the following theorem. Theorem 1: Consider a graph G = (V,E) (with n = V ) with the independence-in-cut | | property. Consider also a source s and a set T = t ,...,t of terminal nodes in G. Let 1 α { } c = minE(C), where is the set of all possible s-t -cuts. Let λ = min (i j) and min 1 C∈C C i,j:P(i↔j)>0P ↔ ǫ = dln(n−2) with 1 < d < λ2(n−2). The s-T-capacity, C , verifies λ2(n−2) ln(n−2) s;T q α C > (1 ǫ)c with probability 1 O , s;T min − − n2d (cid:16) (cid:17) 1 C < (1+ǫ)c with probability 1 O . s;T min − n2d (cid:18) (cid:19) To be able to prove Theorem 1, we first need to state and prove a few auxiliary results. We start by presenting a useful inequality. Lemma 1 (Hoeffding’s inequality, from [22]): For X ,X ,...,X independent random vari- 1 2 m ables with (X [a ,b ]) = 1, i 1,2,...,m , if we define S = X +X + +X , then i i i 1 2 m P ∈ ∀ ∈ { } ··· m (S E(S) mt) exp 2m2t2/ (b a )2 . i i P − ≥ ≤ − − (cid:18) i=1 (cid:19) P 5 First, we determine an upper bound on the probability that the capacity of a cut takes a value much smaller than its expected value. Lemma 2: Consider the single-source single-terminal case. For ǫ > 0 and N 2, we have ≥ that (C (1 ǫ)E C ) e−2(N+x(N−x))ǫ2λ2. x x P ≤ − { } ≤ Proof: We start by writing [C (1 ǫ)E(C )] = [ C E( C ) ǫE(C )]. (1) x x x x x P ≤ − P − − − ≥ To compute the desired upper bound, we shall use the Hoeffding’s inequality (Lemma 1). We have that C = C + C + C . We have that C 0,1 and E(C ) = x si ji jt ab ab ∈ { } i∈Vx j∈Vxi∈Vx j∈Vx (a b). TherefPore P P P P ↔ (a) E(C ) (N x+x(N x)+x)λ = (N +x(N x))λ, x ≥ − − − where (a) followsfrom settingλ = min (i j). Thus, we have that if C E( C ) x x i,j:P(i↔j)>0P ↔ − − − ≥ ǫE(C ), then C E( C ) (N +1+x(N x))ǫλ. Therefore, x x x − − − ≥ − [ C E( C ) ǫE(C )] [ C E( C ) (N +1+x(N x))ǫλ]. x x x x x P − − − ≥ ≤ P − − − ≥ − Moreover, from (1), [C (1 ǫ)E(C )] [ C E( C ) (N +1+x(N x))ǫλ]. (2) x x x x P ≤ − ≤ P − − − ≥ − Now, because the graph G has the independence-in-cut property, C can be viewed as the x sum of N + x(N x) independent Bernoulli distributed random variables. Therefore, we can − apply Lemma 1 to (2), with m = N +x(N x) and t = ǫλ, and we get − 2(N +x(N x))2ǫ2λ2 (C (1 ǫ)E(C )) exp − − = exp 2(N +x(N x))ǫ2λ2 . x x P ≤ − ≤ N +x(N x) − − (cid:18) − (cid:19) (cid:0) (cid:1) Remark 1: The previous result, Lemma 2, is valid for networks where the edges represent links with unitary capacity. In Lemma 1 this corresponds to the case in which all variables X i lie in the unit interval [0,1]. This result (and consequently Theorem 1) can be easily extended for networks with different edge capacities, because Hoeffding’s inequality is valid for variables X [c ,b ], in general. For simplicity, we consider only the case of edges with unitary capacity. i i i ∈ Using the previous result, we obtain another useful inequality. Corollary 1: Let A be the event given by C < (1 ǫ)E C . Then, ( A ) x x x x x { − { }} P ∪ ≤ N 2e−2ǫ2λ2N 1+e−ǫ2λ2N . · Proof:h By Lemmai 2, we have that (A ) e−2(N+x(N−x))ǫ2λ2. Notice that, for each x P ≤ x 0,...,N , there are N cuts in which one of the partitions consists of x nodes and the ∈ { } x (cid:0) (cid:1) 6 source. Therefore, we can write N N N N ( A ) (A ) e−2(N+x(N−x))ǫ2λ2. (3) x x x P ∪ ≤ x P ≤ x x=0(cid:18) (cid:19) x=0(cid:18) (cid:19) X X We have that e−2(N+x(N−x))ǫ2λ2 = e−2ǫ2λ2N−2ǫ2λ2x(N−x) = e−2ǫ2λ2N e−2ǫ2λ2N·NNx(1−Nx). · Setting β = e−2ǫ2λ2N, we get e−2(N+x(N−x))ǫ2λ2 = β βNNx(1−Nx). From (3), we get · N ⌊N/2⌋ N N x x N x x N x x ( A ) β βNN(1−N) = β βNN(1−N) + βNN(1−N) . x x P ∪ ≤ x  x x  x=0(cid:18) (cid:19) x=0 (cid:18) (cid:19) x=⌊N/2⌋+1(cid:18) (cid:19) X X X   Notice that, when x [0,1/2], we have x(1 x) x , and when x [1/2,1], we get N ∈ N − N ≥ 2N N ∈ x(1 x) N−x. Thus, we can write N − N ≥ 2N ⌊N/2⌋ N N x N N−x ( xAx) β βN2N + βN 2N ) P ∪ ≤  x x  x=0 (cid:18) (cid:19) x=⌊N/2⌋+1(cid:18) (cid:19) X X   N N N x N N−x 1 1 = β β2 + β2 x x ! Xx=0(cid:18) (cid:19)(cid:16) (cid:17) Xx=0(cid:18) (cid:19)(cid:16) (cid:17) (=a) 2β(1+ β)N (=b) 2e−2ǫ2λ2N 1+e−ǫ2λ2N N , · p h i where we use the following arguments: m (a) follows from the fact that (y +z)m = m yxzm−x, thus taking m = N, y = β12 = √β x x=0 and z = 1, we get N N β12 x = (1+P√β(cid:0))N(cid:1)and taking m = N, y =1 and z = β12 = √β, x x=0 we get N N βP12 N(cid:0)−x(cid:1)=(cid:16) (1(cid:17)+√β)N; x x=0 (b) followsPfrom(cid:0) s(cid:1)u(cid:16)bstit(cid:17)uting β by e−2ǫ2λ2N. Now, using Corollary 1, we can bound the global minimum cut of G . s N Corollary 2: For all t T, we havethat (C (1 ǫ)c ) 2e−2ǫ2λ2N 1+e−ǫ2λ2N . i ∈ P s,ti ≤ − min ≤ · Proof: LetA˜ betheevent C < (1 ǫ)c andletA betheevent C <h(1 ǫ)E Ci . x x min x x x { − } { − { }} We have that E(C ) c , x 0,...,N, because c = minE(C), where is the set of all x min min ≥ ∀ ∈ C∈C C possible s-t -cuts. Consequently, we have A˜ A , which implies that A˜ A , resulting i x x x x x x ⊆ ∪ ⊆ ∪ in (C (1 ǫ)c ) = ( A˜ ) ( A ). Applying Corollary 1 concludes the proof. P s,ti ≤ − min P ∪x x ≤ P ∪x x We are now ready to prove Theorem 1. 7 Proof of Theorem 1: Replacing ǫ in Corollary 2 by the expression dln(n−2) = NdlnN, λ2(n−2) λ2N we obtain q q P(Cs,ti ≤ (1−ǫ)cmin) ≤ 2e−2λ2Ndλl2nNN ·[1+e−λ2Ndλl2nNN]N = 2e−2dlnN ·[1+e−dlnN]N N 2 1 = 2eln(N−2d) [1+eln(N−d)]N = 1+ . · N2d · Nd (cid:20) (cid:21) N N Using once again the fact that (y+z)N = N yxzN−x, we get 1+ 1 N = N 1 x. x Nd x Nd x=0 x=0 Therefore, we have that P (cid:0) (cid:1) (cid:2) (cid:3) P (cid:0) (cid:1)(cid:0) (cid:1) N x 2 N 1 (C (1 ǫ)c ) P s,ti ≤ − min ≤ N2d · x Nd x=0(cid:18) (cid:19)(cid:18) (cid:19) X ∞ x (a) 2 N 2 1 1 (b) = O = O ≤ N2d · Nd N2d Nd+1 ≈ N2d n2d x=0(cid:18) (cid:19) − (cid:18) (cid:19) (cid:18) (cid:19) X where we used the following arguments: (a) follows from the fact that N = N! = N·(N−1)· ... ·(N−x+1), thus N N (N 1) x (N−x)!x! x! x ≤ · − · ... (N x+1) Nx; (cid:0) (cid:1) (cid:0) (cid:1) · − ≤ ∞ ∞ (b) follows from the fact that yx = 1 , for y < 1, leading to (for d > 1) N x = 1−y | | Nd x=0 x=0 ∞ 1 , which implies thatP2 N x = 2 . P (cid:0) (cid:1) 1−N1−d N2d · Nd N2d−Nd+1 x=0 Using the bounds we have already cPons(cid:0)truc(cid:1)ted for the single-source single-terminal case, we can easily obtain bounds for the single-source multiple-terminals case. Since C = minC , s;T s;ti ti∈T we have that (C (1 ǫ)c ) = C (1 ǫ)c (C (1 ǫ)c ). P s;T ≤ − min P { s;ti ≤ − min} ≤ P s;ti ≤ − min ! t[i∈T tXi∈T By Theorem 4, we have that (C (1 ǫ)c ) = O 1 , t T. Thus, from (4), we P s;ti ≤ − min n2d ∀ i ∈ have that P(Cs;T ≤ (1−ǫ)cmin) = O nα2d . (cid:0) (cid:1) Now, to compute the upper bound(cid:0) on(cid:1) (Cs;T (1 + ǫ)cmin), let C∗ be a cut such that P ≥ E(C∗) = c . Notice that, by definition, any cut is greater or equal to C , in particular the min s;T cut C∗. Thus, if C (1+ǫ)c then C∗ (1+ǫ)c . Therefore, (C (1+ǫ)c ) s;T min min s;T min ≥ ≥ P ≥ ≤ (C∗ (1+ǫ)c ), which is equivalent to min P ≥ (C (1+ǫ)c ) (C∗ c ǫc ). (4) s;T min min min P ≥ ≤ P − ≥ Define δ as thenumberof randomvariables that define thecut C∗, i.e. δ is the numberofedges that possibly cross the cut C∗. Because λ = min (i j), we have that c δλ. Thus, min i,j:P(i↔j)>0P ↔ ≥ if C∗ c ǫc , then C∗ c ǫδλ. Hence (C∗ c ǫc ) (C∗ c ǫδλ) min min min min min min − ≥ − ≥ P − ≥ ≤ P − ≥ and, from (4), 8 (C (1+ǫ)c ) (C∗ c ǫδλ) (5) s;T min min P ≥ ≤ P − ≥ Because the graph G has the independence-in-cut property, C∗ can be viewed as the sum of δ independent and bounded random variables (more precisely, all the variables belong to the interval [0,1]). Thus, noticing that E(C∗) = c and applying Hoeffding’s inequality (Lemma 1) min with m = δ, S = C∗ and t = ǫλ, we have that 2δ2ǫ2λ2 (C∗ c ǫc ) exp = exp 2δǫ2λ2 . min min P − ≥ ≤ − δ − (cid:18) (cid:19) (cid:0) (cid:1) Recall that in a s-t -cut of size x there are N+x(N x) random variables (with N = n 2). i − − Since x 0,...,N , we have that the number of random variables that define a cut is at least ∈ { } N, and this is true for every cut. Thus, the same holds for the cut C∗, which implies that δ N. ≥ This is equivalent to δ n 2, hence ≥ − (C∗ c ǫc ) exp 2(n 2)ǫ2λ2 , min min P − ≥ ≤ − − and thus, from (5), we get (C (1 + ǫ)c )(cid:0) exp( 2(n (cid:1)2)ǫ2λ2). Replacing ǫ by s;T min P ≥ ≤ − − dln(n−2), we obtain λ2(n−2) q dln(n 2) 1 (C (1+ǫ)c ) exp 2(n 2) − λ2 = exp( 2dln(n 2)) = s;T min P ≥ ≤ − − λ2(n 2) − − (n 2)2d (cid:18) − (cid:19) − 1 = O . n2d (cid:4) (cid:18) (cid:19) III. SMALL-WORLD NETWORKS A. Classes of Small-World Networks We start by giving rigorous definitions for the classes of small-world networks under con- sideration. All the models in this paper are consider to be unweighted graphs containing no self-loops or multiple edges. First, we require a precise notion of distance in a ring. Definition 4: Consider a set of n nodes connected by edges that form a ring (see Fig. 3, left plot). The ring distance between two nodes is defined as the minimum number of hops from one node to the other. If we number the nodes in clockwise direction, starting from any node, then the ring distance between nodes i and j is given by d(i,j) = min i j ,n i j . {| − | −| − |} For simplicity, we refer to d(i,j) as the distance between i and j. Next, we define a k- connected ring lattice, which serves as basis for the small-world models used in this paper. 9 Definition 5: A k-connected ring lattice (see Fig. 3) is a graph L = (V ,E ) with nodes V L L L and edges E , in which all nodes in V are placed on a ring and are connected to all the nodes L L within distance k. 2 Notice that in a k-connected ring lattice, all the nodes have degree k. We are now ready to define the small-world models under consideration. Definition 6 (Small-World Network with Shortcuts [18]): We start with a k-connected ring lattice L = (V ,E ) and let E be the set of all possible edges between nodes in V . To L L C L obtain a small-world network with shortcuts, we add to the ring lattice L each edge e E E C L ∈ \ with probability p. Definition 7 (Small-World Network with Rewiring): Consider a k-connected ring lattice L = (V ,E ). To obtain a small-world network with rewiring, we proceed as follows. Let E = E L L R L be the initial set of edges. Each edge e E is removed from the set E with probability 1 p, L R ∈ − where p is called the probability of rewiring. Each edge e / E is then added to the set E with L R ∈ probability pk . After considering all possible edges connecting nodes in V , the resulting n−k−1 L small-world network is specified by the graph (V ,E ). L R This model is a variant of the small-world network with rewiring in [12] in which all the edges can be viewed as independent random variables, thus satisfying the independence-in-cut property. Finding max-flow min-cut bounds for the original construction is intractable due to the complex dependencies between randomly rewired edges. To ensure the key property of constant average number of edges per node, as in [12], our definition attributes weight pk to the edges n−k−1 that are not in the initial lattice. The expected number of edges per node in an instance of the model is thus given by (1 p)k + pk (n k 1) = k. − n−k−1 − − B. Capacity Bounds for Small-World Networks We shall now use Theorem 1 to prove capacity bounds for the aforementioned small-world models. We start with a useful lemma. Lemma 3: Let L = (V ,E ) be a k-connected ring lattice and let G = (V ,E) be a fully L L L connected graph (without self-loops), in which edges e E have weight w 0 and edges L 1 ∈ ≥ f / E have weight w 0. Then, the global minimum cut in G is kw +(n 1 k)w . L 2 1 2 ∈ ≥ − − Proof: We start by splittingG into two subgraphs: a k-connected ring latticeL with weights w and a graph F with nodes V and all remaining edges of weight w . Clearly, the value of a 1 L 2 10