Network Failure Detection and Graph Connectivity
Jon Kleinberg Mark Sandler Aleksandrs Slivkins
Department of Computer Science Cornell University, Ithaca, NY 14853 kleinber, sandler, slivkins @cs.cornell.edu
1 Introduction
в б

Abstract We consider a model for monitoring the connectivity of a network subject to node or edge failures. In particular, we are concerned with detecting -failures: events in which an adversary deletes up to network elements (nodes or edges), after which there are two sets of nodes and , each at least an fraction of the network, that are disconnected from one another. We say that a set of nodes is an -detection set if, for any -failure of the network, some two nodes in are no longer able to communicate; in this way, "witnesses" any such failure. Recent results show that for any graph , there is an -detection set of size bounded by a polynomial in and , independent of the size of . In this paper, we expose some relationships between bounds on detection sets and the edge-connectivity and node-connectivity of the underlying graph. Specifically, we show that detection set bounds can be made considerably stronger when parameterized by these connectivity values. We show that for an adversary that can delete edges, there is always a detection set of size which can be found by random sampling. Moreover, an -detection set of minimum size (which is at most ) can be computed in polynomial time. A crucial point is that these bounds are independent not just of the size of but also of the value of . Extending these bounds to node failures is much more challenging. The most technically difficult result of this paper is that a random sample of nodes is a detection set for adversaries that can delete a number of nodes up to , the node-connectivity. For the case of edge-failures we use VC-dimension techniques and the cactus representation of all minimum edge-cuts of a graph; for node failures, we develop a novel approach for working with the much more complex set of all minimum node-cuts of a graph.
   ижд йзег  жд 4г  % 61)& % 5#" 2 0( 2г и   2 0 (& $ г 3% #1)'% з#" %2    ижд йзег  ижд ег  д и и !  ижд г !  д 

Monitoring network connectivity. As links or nodes fail in a network, it is important to maintain information about basic properties such as connectivity. For large, unstructured networks, this is often done by recourse to sampling and other approximate measurements; performing such measurements in a robust and accurate way is an active research topic (e.g. [4, 5, 17, 19, 18]). A general problem here is to minimize the cost of network monitoring and measurement, in terms of communication, computation, and resource usage. Here we consider a recently proposed model for monitoring network connectivity [14]. We are given a connected node graph on nodes, and we want to detect "failure events" in which at most network elements (nodes or edges) are deleted, after which there are two sets of nodes and , each of size , such that no node in has a path to any node in . We will call such a pair of sets separated, and we will call such an event an -failure. (To reflect the fact that the node or edge failures can be arbitrary, we will sometimes speak of them as being selected by an adversary.) To detect such failures, we consider the strategy of placing "detectors" at a subset of the nodes of . Now, if we find that two detectors are unable to communicate -- either because there is no path between them, or because one has been deleted -- we can record a fault in the network. We would like our set to have the property that whenever an -failure occurs, some two detectors are unable to communicate; we will refer to such a set as an detection set. Note the nature of this condition: must detect all possible -failures, so we imagine as being chosen before the adversary selects a set of network elements to delete. The emphasis in [14] was on finding a bound on the number of nodes that must be randomly selected from a graph in order to obtain an -detection set with high probability. Improvements to these bounds were obtained by [7]. In this paper, we adopt a somewhat different approach to This work has been supported in part by a David and Lucile Packard this issue, by exposing some interesting and non-trivial conFoundation Fellowship and NSF ITR/IM Grant IIS-0081334. Full version nections between the size of the smallest detection set for a is available at http://www.cs.cornell.edu/people/slivkins/research/.
 ижд г    и  ижд йг   ижд йзег   и 8д @9 и  ижд г    8   ижд г   7

Copyright й 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

76

 
1 Note that no such simple bound is available for the case of nodefailures, which is yet another evidence of its difficulty.

77

 ижд г

 !жд 4ег e fd

8 0( Apcb& % $ #" г

 1% $ #" г


 4йзег ижд


 !жд 4г

 % 5#" 2г

 8 Sдг " ATйе#RQ! P  ижд йг ` W

!


 3% 2

X YWи V


0 (& 1)U% 2 #" г

 ижд г

 %2

!

0 (& и 0 ( cbaa1)& % $ #" г


 ижд йг

! и

8 д

h i2

g е%

graph and the values of its edge- and node-connectivity. (The edge-connectivity of , denoted , is the smallest number of edges that must be deleted in order to disconnect . The node-connectivity of , denoted , is the analogous quantity for node deletions.) We show that stronger bounds on detection set size can be obtained if we parameterize these bounds by the connectivity values and ; and for some cases, we use this relationship with connectivity to provide the first per-instance guarantees for detection sets. Because our results are different depending on whether the adversary is deleting edges or nodes, we consider these two cases separately. Detection sets for edge failures. We begin with adversaries that can delete up to edges; as such, we will be concerned with -edge-failures, which are -failures in which only edges are deleted. It is known that a random set of nodes is an -detection set for edge failures with high probability [14], and that every graph contains an -detection set for edge failures of size [7]; note that both bounds are independent of the size of the graph . It is not difficult to show that both bounds are tight, and so there is no prospect of obtaining an improvement that applies to all graphs. However, it makes sense to ask whether better bounds are possible in terms of natural parameters of the graph . An obvious parameter to consider here is the edgeconnectivity ; indeed, there can be no -edge-failures in if . Our first main result establishes that is indeed a natural way to parameterize the problem; we show that every graph has an -detection set for edge failures of size at most . Note that there is no leading constant in this bound, and that it is independent not just of the size of but also of the value of . Extending this result, we show further that an -detection set for edge failures of minimum size for a graph can be computed in polynomial time. The algorithms used to establish these results are based on the cactus representation of all minimum edge-cuts of [6, 8]. Given that strong bounds are possible for detecting an adversary that can delete one minimum cut's worth of edges, it is natural to ask what can be said about an adversary capable of deleting a number of edges equal to times the size of a minimum cut. We show that a random set of nodes is a -detection set for edge failures with high probability. This is essentially a factor of times stronger than the bounds of [7, 14], which do not take edge connectivity into account. Our proof of this result uses a VCdimension argument in the style of [14]; the bound on the VC-dimension is obtained using a result of Mader [16, 9]. that extends results of Lovasz [15] and of Cherkasskij [3] on ┤ edge-disjoint paths in graphs. Detection sets for node failures. We now consider adversaries that can delete up to nodes. By analogy with our results for edge failures, we consider the size of detection
 ! и   % з#" $г   ижд г  г BеA!  г BеA  ижд ег и  ижд г  дж IHGг и и   жд Fйг  ижд г  % 61)& % з#" 2 0( $г   жд Fйзег  % 61)& % з#" 2 0( $г EDи C  ижд г    %2  

sets in terms of the node-connectivity . Our main result here is that every graph (with ) has an detection set for node failures of size ; moreover, a random set of nodes forms an -detection set for node failures with high probability. Again, note that these bounds are independent not just of the size of but also of the value of . Extending our results to adversaries that delete nodes for is a very interesting and apparently difficult open question. We note the distinction, raised by Gupta [7], between strong and weak detection sets for node failures. A strong has the property that, after any detection set node-failure, two nodes of lie in different connected components. A weak detection set has the property that, after any -node-failure, two nodes of lie in different connected components or an element of has been deleted. Either of these definitions arguably forms a plausible definition of network failure detection. Improving a bound of [14], Fakcharoenphol showed that a random set of nodes is a strong -detection set for node failures [7], and Gupta showed that every graph has a weak -detection set for node failures of size . As we note in Section 4, weak detection appears to be a more useful notion when the problem is parameterized by node connectivity; in particular, our main result is about weak detection sets. Henceforth, we will assume that all detection sets for node failures are weak unless otherwise specified. Our analysis for node failures is significantly more complicated than for edge failures, and this is not surprising; not only is no analogue of the cactus representation known for min-node-cuts, but this appears to be intrinsic due to the completeness of even counting the number of min-node-cuts [2]. Indeed, given the lack of tractable representations for min-node-cuts, we believe that our analysis develops some useful properties of their structure. We begin by constructing a detection set of minimum size for adversaries that can delete shredders [2, 13] -- min-node-cuts whose deletion produces at least three components. The construction of the detection set then proceeds by greedily isolating a maximal collection of relatively balanced min-node-cuts that produce just two components, and whose "small sides" are disjoint; the small side of each such cut is required to have at least nodes. We then show that by placing detectors so that one lies on the small side of each of these cuts, there is no way for a min-node-cut producing two components of size at least each to avoid being detected. Further Discussion. A simple calculation based on Karger's algorithm gives an upper bound of on a random sample of nodes that forms an -detection set for edge failures.1 However, our goal in this paper is to


FAC T 2 . 1 . Suppose is a tight set in cactus , is a branch node. Then: (a) if then contains at least one -component. (b) if then is contained in a -component. (c) for any -component of , either , or , or , or .
 ih     h nmYq     mlk q h      ed  f eg  j h

The proofs are not difficult; they are omitted due to space limitations. Let be a weighted graph on vertices. A cactuspair of is a pair where is a cactus, and is a mapping from to such that if is a tight set in then is a tight set in . For each tight set of say that represents the min-cut of such is a -component. A cactus representation that 2 Detection sets for edge failures of is a cactus-pair of that represents all min-cuts of In this section all cuts are edge-cuts, and all detection sets . Dinits et al. [6] proved that every capacitated graph has are for edge failures. Let be a set of nodes, representing a cactus representation of size . Further results show the locations of our detectors. detects a cut if some pair that a cactus representation of size can be efficiently of detectors is separated in . is an -detection constructed. See the introduction of [8] for discussion. set if it detects every -edge-cut. Balanced cactus representation. Here we are only inThere are two subsections. In the first one we construct terested in -balanced min-cuts, and so the cactus represena smallest -detection set and prove it has size . In tation is too general for our purposes. This motivates the the second one we prove that a set of randomly following definitions. sampled nodes is an -detection set with high probabilLet an -cactus-pair be a cactus-pair that represents ity. all -balanced min-cuts. Let an -cactus be the cactus in such cactus-pair (if the mapping is clear). A subset
 p   s  8г Ao#"  8  8г Ao#"  д  г rWq   pж  Aqoг  pж  Auг  г BDq   Rег 2 'p s t  Rег 2 'p s t д д    д   s   %2  r  ижд йзег  %2 01()& % $  #" г   ижд ег       ижд г  ижд г       w   жд Fйг   и Er    

78


find bounds that do not depend on the size of the graph. Following [14], we can extend our results to a model in which the nodes of the network are partitioned into two sets -- a set of end nodes and a set of internal nodes. We assume that we are only allowed to place detectors at end nodes, and correspondingly are only interested in monitoring the connectivity of the end nodes. Specifically, we re-define -failures as failures of network elements, after which two disjoint subsets of , each of size , are separated from each other. We can show that the bounds obtained above carry over to this more general setting; we omit further discussion of the generalization from this version of the paper. Our work is similar in spirit to some of the work on vertex connectivity and augmentation thereof, e.g. [12, 2, 13, 11]. The actual technical issues are quite different, however, since we are only interested in balanced cuts. In general one could view our work here as integrating notions from edge- and node-connectivity with the problem of balanced separators of graphs -- two topics that have traditionally been approached separately due to their great differences in tractability. Notation. In this paper all graphs are assumed undi. An rected; our standard notation for a graph is edge(node)-cut is a set of edges (nodes) such that is disconnected. A min-edge(node)-cut is an edge(node)-cut of minimum size. This size is also known as edge(node)- connectivity and denoted by and respectively. We will write min-cut when it is clear whether we are talking about edge-cuts or node-cuts. A set of nodes is tight if it is a union of some (but not all) components of a min-cut. A cut is called balanced if there are two sets of vertices of size that are disconnected from one another in . An -balanced cut of edges(nodes) is called an -cut. If sets , have a non-empty intersection, we say meets . To help clarify the notation in places, we will sometimes write to denote the union of disjoint sets and , and to denote the difference of sets and for which .
д   u  xж qг ypGwv P 8д @9 h q 5t9 uд д   E 2 q  и sr h q  ! h q  ижд г

2.1 Detection sets for min-edge-cuts Cactus representation. To make the presentation selfcontained, we describe some basic properties of cactus graphs and the cactus representation of minimum cuts; see [6, 8] for more details. In this exposition, edges will be viewed as cycles of length two; cycles of length 3 or more are called proper. A cactus is a connected graph such that any two of its cycles have at most one vertex in common. An arbitrary cactus can be obtained starting from a cycle and recursively adding new cycles that share a single vertex with the existing graph. In a cactus, some edges are contained in a proper cycle (cycle edges), and some aren't (path edges). Suppose we give each cycle edge capacity 1/2, and each path edge capacity 1. Then one can show that the min-cuts of a cactus have capacity 1: each path edge is a min-cut; any pair of cycle edges from the same cycle is a min-cut; and there are no other min-cuts. In a cactus, nodes of degree one will be called leaves, nodes of degree two that are contained in a cycle will be called cycle nodes, and all other nodes will be called branch nodes. Consider a branch node of a cactus . It connects two or more cycles. One can show that the removal of splits into two or more connected components ( -components ). Each -component is tight: for some cycle containing , it is obtained by removing the edge(s) of that are adjacent to .


Figure 1: An -cactus with detectors. Branch nodes are denoted by ' ', detectors by '*'. In the central cycle, there are three subcycles between the branch nodes. The smallest L E M M A 2 . 1 . Suppose is an -cactus, is a branch node, of them is not heavy, hence does not contain a detector. The is a -component that is not heavy. Let be with other two are big enough so that they need two detectors contracted into . Then is also an -cactus. Proof: For each -balanced min-cut of there is a min- each. Each of the three smaller cycles is heavy (even cut of that represents it. By Fact 2.1c there is a without its branch node), since otherwise it would have been component of such that or . Since contracted. is heavy and isn't, it must be the case that is a proper subset of . Then , so is a min-cut in , too. Therefore represents . (3) Suppose a detector is mapped to a branch node of . By analogy with (1), we claim that is also an Characterizing detection sets for min-cuts. Let be -detection set. For suppose not. Then is disjoint be a reduced -cactus-pair with some balanced tight set . Let a capacitated graph. Let . Since of . We will characterize -detection sets of minimum is an -detection set, , so . Therefore size in terms of . by Fact 2.1a contains some -component . Since is Let a subcycle be a set of consecutive cycle nodes of a reduced, is heavy, so there is a detector mapped to it. So (proper) cycle in . Consider the non-degenerate case when contains a detector other than , a contradiction. there is at least one branch node. Then the weight In view of (1-3), we see that is -canonical. of each leaf and each subcycle is at most . Let a canonical subcactus be a set of nodes of that contains each L E M M A 2 . 3 . Any -canonical set is an -detection set. leaf, has an element in every heavy subcycle, and contains Proof: Suppose and meets each leaf and each no branch nodes. Let be a set of detectors(not heavy subcycle of . We need to prove that meets each necessarily an -detection set). Say is -canonical if heavy tight set of . To show this we claim that any heavy is a canonical subcactus, and at most one detector is tight set of contains a leaf or a heavy subcycle. mapped to each node of . The following two lemmas show We'll use induction on the size of . The base case that any smallest -detection set is in fact a smallest - corresponds to an that consists of one vertex, say . By canonical set. Fact 2.1a cannot be a branch node. So either is a leaf or Call heavy if , and balanced if both it is a heavy subcycle consisting of a single cycle node. and are heavy. Call balanced if For the induction step, note that if contains a branch is balanced. For each balanced tight set of let be node then by Fact 2.1a contains some (heavy) . a (balanced) tight set of such that component, to which the induction hypothesis applies. If does not contain a branch node then it lies within a single L E M M A 2 . 2 . Any smallest -detection set is - cycle, so is a (heavy) subcycle. The claim follows. canonical. Proof: Let be a smallest -detection set. Call elements of detectors. We need to prove that (1) at most T H E O R E M 2 . 1 . A smallest -detection set is of size at one detector is mapped to each node of , (2) there is a most . There is a polynomial-time algorithm to construct detector mapped to each leaf and each heavy subcycle of , it. (3) and no detectors are mapped to branch nodes of . We'll Proof: Let be a reduced -cactus-pair of . We prove these three statements in order. have seen that smallest -detection sets are (mapped to) (1) Suppose two detectors , map to a node of smallest canonical subcacti of . Therefore it suffices to . To obtain a contradiction it suffices to show an - compute a smallest canonical subcactus of . detection set smaller than . We claim that is also Let be a subset of a proper cycle in . Call an -detection set. Suppose not. Then there is a balanced a -detection set if does not contain any branch nodes, tight set of that contains . Obviously . and every heavy subcycle of contains an element of . Let . Since , , so , By definition, if there are no heavy subcycles in then an too, a contradiction. empty set is a -detection set. Obviously, a subset of is (2) There is a detector mapped to each heavy tight set of a canonical subcactus iff it is a union of leaves of and , in particular, to each leaf and each heavy subcycle. (disjoint) -detection sets, one for each proper cycle of .
  } }             г` p pGGHt P`       г Dеpp  `  ` `  t   жд Fйг      д  г Dpp  t    жд 4г        жд 4г  q E h     pж  Auxoг   д  `    ` p `  жд 4г       %2  жд 4ег     u ~ Tг 2 'p u t `  )pег 2 'p t  }  жд 4ег   Ef   g     pег ` p   ` x 2 2  2 `  Gг 2 'm tp P   8д iIBuг X  n   {{ h `  gx д  ` x       S   г p еpD P 2  kz h  г q rol h` S  д  жд 4ег      жд 4ег ` y 8д l u 9u  г q BеWtw h 2   жд 4г  pж  Auxoг д     ` x  w|  S     `   жд 4г ` y  жд 4г д     q lY h  г` p pеHH P`    ` x      Yq   жд 4ег ` y  г Dpp     

of vertices of a cactus is heavy if . Call a cactus-pair reduced if every -component is heavy. A reduced -cactus-pair can be efficiently computed from a standard cactus representation by consecutively applying the following reduction.
8д wDTvег 2 t p u 9 u   д

79


T H E O R E M 2 . 3 . [16] The maximal number of edge-disjoint -paths is , where the minimum is taken over all collections of disjoint subsets of vertices such that . edge-disjoint -paths. C O RO L L A RY 2 . 1 . There are Proof: Consider a collection of disjoint subsets of vertices such that . Let , . By the above theorem it suffices to prove that . Note that since . Let be the such that is odd. All edges components of exiting each are to . So . If then . If then . Therefore . The following is a well-known application of the probabilistic method. L E M M A 2 . 4 . Let be a multi-graph on . Then there exists a partition of into sets such that there are at least edges between and . . L E M M A 2 . 5 . The VC-dimension of is Proof: Let be a subset of of size . By Cor. 2.1 there exists a family of edge-disjoint -paths. Let be a multi-graph on such that there is a 1-1 correspondence between -paths in and edges . By Lemma 2.4 there exists a partition of into sets such that (in the original graph) there are edge-disjoint paths between and . We can choose so that there is guaranteed to be a family of (at least) edge-disjoint paths between and . We claim that cannot be shattered by . Suppose not. Then there exists such that . is a union of components of some cut of or less edges. is disjoint with (at least) one path . The ends of are in the same -component, so either they are both in , or both not in . In both cases this contradicts . Thus, the claim is proved, and it follows that the VC-dimension of is . 3 Detection sets for node failures The main theorem of this section (Thm. 3.2) is that for a set of randomly sampled nodes is a weak -detection set with high probability. We rely
 %2 0( 1)& % 2 #" г  !жд 4ег  8 Sдг " Aзе#┤R! C  ж л Bq6ег }   ╞ 2 2 л R╜t P л  л ╗ P л г  $ #" X xи  S  $ 6┼vм г─ P  F├ л ж л м и 2 `┬ yeQ╞ л    43y╣ мг q ` y┬ л  43y╣ мг S  ┼  л ┬ л л 2 л ┬  $ #Bм г" P л S  F├  л  2 л  л S S л qж л 2 л 2 л  ж л Bq6г л u W u 2 S ╡ qг GF } 9 ╡ г  fiaе4┤wfiFе4v │ 9 ╡ q ╢г  9  F║oyyB мг ╣ Pо о ┐#м C └ ╖╖ йTT╖ │ л P  2 X WG┴6╗D║fB  гм 9о м9о   г е4 X ╝#╗AFq u Pu л ╡ iFе4 9 ╡ qг  F║y╣ мг X WG┴f╗W║f╗B  гм 9о о 9о ╡q╢  mY ╡q ╢ ║┐W м 9 ╡ a  F║y╗B мг ╣ Pо ╕ qж ╖╖╖ йTзTж  ╡Fq╢егп╛╜о о P 2 S q йж q о ┐fм 9 ║о ╡ q ╢г о uGпwWiGF┤г  ╡ qг  │ X |1dFq u Pu л ╡ ▓▒ ░ )#pS 2 ╕ qж ╖╖╖ йTзTж S q йж 2 q л

2.2 Smaller detection sets for edge failures A set of nodes is -edge-separable if there exists a set of edges such that is a union of components of . Let be the family of all -edge-separable sets. We say that is shattered by if for all there exists an such that . The VC-dimension of is defined to be the maximum cardinality of a subset of that is shattered by . In [14], it was shown that one can connect the VCdimension of with -detection sets via the notion of an -net, which is a set that meets each of size . Specifically, a theorem by [1] says that a set of randomly sampled nodes is an -net for with probability at least .2 Moreover, it is easy to show [14] that an -net for is an -detection set. In [14], it was shown that the VC-dimension of is at most , yielding a bound of on the size of an -detection set. In this section, we strengthen the VCdimension bound on to . As a consequence, we will obtain the following theorem. T H E O R E M 2 . 2 . A set of randomly sampled nodes is an -detection set with high probability.
2 [14,

7] used a slightly weaker theorem, with a corresponding bound of .

80

 лг 4

л

 г GF

м

 лг по

q

л

л | 


л

л

Therefore to compute a smallest canonical subcactus of it suffices to construct a smallest -detection set for each proper cycle of . The construction is as follows. Assuming consists of more than one cycle, contains one or more branch nodes. Assuming contains cycle nodes, pick any branch node followed by a cycle node . Start with . In the iterative step, start with a cycle node and move clockwise along till a heavy subcycle is detected (call this subcycle selected ) or a branch node is reached. Start a new step with the next cycle node. Stop when is reached. Let be the set of the last nodes (clockwise) of selected subcycles. Obviously is a -detection set. is a smallest such set by the following observation. Let be a -detection set. Let be a branch node or an element of . Let be the next node clockwise. Let be the smallest heavy subcycle starting with , if it exists. Let be the last node of . Then contains at least one element of . The observation is that is a -detection set with the same or smaller number of elements. Consecutively applying this observation, we can transform to without increasing the number of detectors. Our construction puts one detector into each leaf of and each selected subcycle. Since leaves of are heavy and selected subcycles are heavy and disjoint, our construction covers at least weight with each detector. Since the total weight of (nodes of) is , the total number of detectors is at most .
 1 ` }      `   ` p       `    `   ` y   8      HyU ` `  8 д  `   %2  W ` y

We now turn to the new bound on the VC-dimension; to prove it, we will use the following theorem by Mader [16] on edge-disjoint paths between elements of a given set of vertices. Let be a subset of of size . Let be the number of edges leaving . Let be the number of components of for which is odd. Let an -path be a path connecting distinct elements of .


q t  д 

 w

и r 

 l 


 2 0 (& $ г 3% 6cb'% з#"

 
 ижд йг


 %2

q

0( 1)& % $  #" г

 X

 $ #" г

  
 ижд г


 #1)A% y% 6cb% з#" 2 0 ( & 2  2 0 (&  г

к 1й и ж е г ив xIдpв Iдв qa з б ж ег б  

д


 ижд ег

 yd P

и


X Yy1 и


и

 ижд г

д

8д 9 


For a family of -shredders, we call a component of a shredder an -head if it meets at least one shredder in . Now, suppose we have an -detection set for shredders, and is an -shredder with an -head . Then there exists that meets ; so by Lemma 3.2 contains all components but one, and hence contains a detector. This gives the following lemma. L E M M A 3 . 3 . Let be a family of -shredders, with , and let be an -shredder with an -head . Then any detection set for meets .
8д qe! C д ═  д h ═   д     ═ ═  ижд йзег  д ═   д  ┐┤  

Proof of Thm. 3.1: Let be the family of all -shredders. . While there exists an -shredder Start with be 3.1 Strong detection sets for shredders It is a well- with two or more -heads, delete from . Let the resulting family of shredders. By Lemma 3.3 any strong known fact that there can be exponentially many min-cuts. is a strong detection set for . Furthermore, even counting min-cuts is #P-complete [2]. detection set for Let . Let the head of be the (single) However, there can be only shredders [13], with a head of . Let the tail of be . Note that by polynomial-time enumeration algorithm [2]. We start by Lemma 3.2 for any the tail of is contained stating the main result of this subsection. in the head of (and vice versa). In particular, tails are pairwise disjoint. Since each head contains someone else's T H E O R E M 3 . 1 . Suppose . Then a set of of nodes is a detection set for iff meets randomly sampled nodes is a strong detection set for - tail, a set the tail of each . Therefore, a smallest detection shredders with probability at least . Moreover, a set for has size . Since tails are of size each, smallest strong detection set for -shredders has size . The random sampling result follows by a simple and can be constructed in polynomial time. probabilistic computation. Before we prove this theorem we need to establish some the connected 3.2 Detecting two-way min-cuts We now construct a basic facts about min-cuts. For a cut -cuts. First we give components of are also called -components . Let weak detection set for two-way , be min-cuts. Say meshes if meets at least two a non-efficient deterministic construction. We consider -cuts and use a greedy-type algorithm to construct a -components. By [2, Lemma 4.3(1)] if meshes then -cuts with sides and meets every -component. Thus meshing is a symmetric "maximal" family of two-way such that for all . In particular 's are relation. If meshes (and meshes ), the two cuts are pairwise disjoint, so there are at most of them. It turns meshing. Else and are non-meshing . out that if then putting a detector into each L E M M A 3 . 1 . ([2], Lemma 4.3(2)) If min-cuts and are suffices. More precisely we show (Thm. 3.3) that these demeshing, then there is a component of either or such tectors together with any weak detection set for shredders give a weak -detection set. Then a simple probabilistic that contains . argument yields the following result. C O RO L L A RY 3 . 1 . If then any two -shredders are non-meshing. T H E O R E M 3 . 2 . Suppose . Then a set of randomly sampled nodes is a weak L E M M A 3 . 2 . Let and be non-meshing shredders. Let detection set with probability at least . be the -component that meets . Then contains all -components but one, call it . Moreover, contains We start with some notation and a simple but very useful , i.e. all -components other than . lemma about crossing min-cuts. Let be a set of nodes. Call Proof: Pick any . By minimality of , has connected if the subgraph of induced by is connected. edges to each -component (else, is a cut). Thus, Else say is disconnected . Say a cut preserves if is connected. Since , disjoint with and lies in one component of . Note
╡ x }  !жд 4ег 2  ┐   2 ╡ x  ╡ x  8д @9    h  2     ═ ┐┐╛q   д  ╗╟X h% i2    !жд 4ег g╘ uе% hS  ! 4ж  ╙ D╥ fP h i2 ═ % 2 C  г  t╬q'  ж  ! 2 u  t╧   8 Sдг " ATй#j! C 2 ╤ wBx ╡ u   2 h  !жд 4ег   t P 2   ╛     1)H% 5#" 2% 0 ( & 2 г   2  %2  ! 4ж r Hu 2 h i2 ╡ ╨ % u г   2% % r 2 д  YY╠╦ ╢  h г 0( 1)& % 2 #"      ` y     д  wQX          ╚   8г A#"  д ` y 8д EQ! C   Ev    8д ╛! C  mlq      yv  ╩╔ Fз┤w|w{q             mYq ╚      

81

}


` yE|m╗Y┐vmYq h   q h 


 mq  ` y

on a special case of -shredders, which is a corollary of our result on strong detection thereof (Thm. 3.1). Before we proceed, let's review the definitions. In this section all cuts are node-cuts, all detection sets are for node failures. A cut is called two-way if has exactly two connected components, called the sides of . A shredder is a min-cut with three or more components. An -shredder is an -balanced shredder. A set of nodes strongly detects a cut if some pair of detectors is separated in . If either meets or strongly detects , say weakly detects . detects (is a detection set for) a family of cuts if it detects every cut in the family. The rest of this section is organized as follows. In the first subsection we show how to find a strong detection sets for -shredders. In the second we use shredders to get a detection set for two-way -balanced min-cuts. Combining these two results gives us the main theorem.
   ╟ д   'n    д д  д  д 

is connected, and hence lies in a -component . So all other -components are contained in and .


Construction 1. Let denote family of all -balanced two-way mincuts, and let denote the family of the sides of all . Stop if is empty. 2. Choose any inclusion-wise minimal component from , let be the corresponding cut and be the second component of . Put detectors in and .
h   h  h 2  г oWт   ╜  %

Figure 2: Two applications of the Two-Quarters Lemma. To formulate the promised lemma, we will use the and are respectively following notation. The sides of , and , . Their intersections ("quarters") are . Also let and and . L E M M A 3 . 4 . ( T H E T W O - Q UA RT E R S L E M M A ) Suppose two-way min-cuts and are weakly crossing so that the and are non-empty. Then two quarters (a) and , (b) and are tight, with , (c) is connected, same for . Proof: and separate and respectively from the rest of the graph. It follows that (else ), (else ), (else ) and (else ). Therefore and , so and are mincuts and and are tight. Finally, is connected as a union of two connected sets ( and ) with a non-empty intersection ( ).
 2S } u  U╫ u u Cu S u d wHf u u Cu 2S   ╡ e  г ╒ еjm S2 ╤   ╤ E ╡  P  2  ╚ 2S  #  Yq ╫ 2 2 2  6  R9 г еn╒  R9 u S S u  v1u u P 2  EY╫ P 2 S S2   v1u u P   u  tдf u u Cu S u  S  2S u ╜ A╫ u u Cu u S2  # г ╒ Gjm S2  u 2 2S S u  |1u u P  6  2    v1u u P 2S  2S 2 2  ┐ P  mYq 2S  S S2 u  l9 2  u S S2  |9 S   S   ╡e #F P╡   ╡ ╚ #A P╡  S ╚ 2 ╤ ╚ ╡e rDE╨╓ P ╤╡ 2 S ╚ e e  d@ P 

A0

B0

Figure 3: Partitioning of the graph after the th iteration of the algorithm By construction all 's are pairwise disjoint, and each . Therefore our algorithm will terminate after at most steps after putting at most detectors. Denote this set of detectors by . Let be any weak detection set for shredders, . T H E O R E M 3 . 3 . If then any -balanced two-way min-cut is weakly detected by .
д ф 8 hS r ! h% i2 2 ф ╘ е% ╡ x S ф W╢ S ф 2 ф ┐╛ф P h i2 % h% i2 9╡ ╜r ╥

This lemma is similar to the result of Jordan [12] on ┤ intersecting tight sets. Note that if and are strongly This is the main technical theorem. Before proving it we crossing our lemma yields will state some simple properties of our construction. (Fig. 2a). We will also use it for -balanced min-cuts . In particular is that are crossing weakly but not strongly. Then one of the L E M M A 3 . 5 . For all disjoint with .
╡  ╙ fP r╥
3 Note that if meets both sides of , say at and , respectively, then meets both sides of . Indeed, for the sake of contradiction suppose does not meet a side of . Then, since any node in has at least one edge to and is connected, there is a path in , contradiction.

82

╥ ┐╙ C

╥ D╙ r

╡ r╟ ╤

╤ ╟

Proof: We will prove that for any , (which would immediately imply then by construction is disjoint with all
╡ # ╤ ╟

is disjoint with ). If for and

╡ #

╡ ╨t╟w╜╥ ╤╙ fP

...

X0

Ai Ai-1 A1

...


╡  ╢~~~ xyuTз╢

2

 y╢

╡ x

5. Put a detector into do not preserve else iterate.
h 

. Remove from all cuts which . Stop If is empty;

╡


╡

г  ofP

╡


 у 

╡


╤ 

 г ╗oy

u

S

 ╪yu u P

2

 ┘yu u P

▌ ▐▄

█с р

┌


и▄

S

h 2


%

 ╪6u u P


▌ ▐▄ и ▄


█

2

u

┌

┌

и▀

и▀

┌


и▀


(a)

,

strongly crossing

(b)

,

weakly crossing

╡

г y

 e

╡


C21

C22

C21

C22

4. Start with the first iteration. For the -th iteration choose a cut so that does not contain any other for . Let . Let be the other side of .
╥


 г y

 ╜╝

h


P1 XP 2

P1 XP 2

3. Delete from let .

h


h


C11

C12

C12

all cuts which do not preserve . For be the side of that does not contain

h


h


Q1 Q2


h

г ╒ jYP

h


 г #Wт

Y Q1 Q2

Y

2S


h 2

C e!

2 2


S2


that a connected set of nodes is preserved by if and only if it is disjoint with . denotes the set of neighbors of , i.e. the set of all nodes in that have an edge to . Note that if is non-empty then is a cut. Say two-way min-cuts and are strongly crossing if each side of meets each side of . Say and are weakly crossing if meets both sides of and vice versa.3 It is easy to see that strong crossing implies weak crossing, but not the other way round.
   г pGj╒       n|q   г vеj╒  г ╒    pеjedeq    

"quarters", say , is empty, so, assuming , are not (Fig. 2b). Now we are ready to describe the construction.

g е%

and

█

█


83

╤

 ╤ г ╒ ynte P╤


The last transition is because . We will prove by induction that each nected and corresponding cut every .
8 hS r Q! Єr╙r nW6Ё

is tight, conis two-way for

╤

8

г ╒ j╛P

д

ЁX ё 9

Ё зX

д

╤

! ╜8

э )╡


╘ %

д

2

Ё X

я ┴4# u 9 u э╡

ч

ь╤

ц

 wn╛P  

ы╡  ╖ ╖ ╖ )uзTTж ╘ q ╡  ж ъ╡

2

╤

ч

ю

ь

╤

u 5g R┴y u u 9u╤

 
╤


╤ YP  q


╤


(see Fig. 4a), and this contradicts the stopping condition of the algorithm. If strongly crosses exactly one , then we replace by the cut (see Fig. 4b). does not strongly cross any , so we apply the argument from the case above to show that is detected. Therefore there is at least one detector in set , which contradicts our assumption. Finally if none of these two cases apply then strongly crosses at least two sets among , say and . An argument using the Two-Quarters Lemma then shows that and partition into the same subsets (see Fig. 4c). We then prove that and cut off a
` B ╡  ╡  ╩╡ ╤ y  з╔ ╡   G╨nyB г ╒ P` ╡  ` B   ╡  ╤ f  ╡  h 2  ╤  

Let with . Let

be all cuts which are intersecting , and . First of all

╡

}


%

h i2


щ

   ╡ г DQ╨j╒


 @@f   

 
h 2

g е%


╡

╡

   ╡ г djrеj╒

╢ ed

╡ 

9u  ╡ UggHx u


 ╡ Qr

 Y 


╡


 ┤ 

h i2

g %

╡ #

╡ 

 {ф h

╡

╡ 

 '╢

%

h 2 щ

 ╡ ╗r

ф

╡ #

╡


╡ x

╡

╡

д


De4╡rгj╒ h2 щ

╡

д

╡

 ╜lеj╒ г


8

%


9u  ╡ Uggд╨ u


╥

╡

 ╡ Ur

!


%

h 2 щ


}

}

! 4ж

╡

 R 

ф


 Etф h

╡  ╢  г Gydn╒

2


The next lemma makes use of the minimality of the sets
h i2 g % 9 ╡ xl@ h

L E M M A 3 . 8 . Suppose is -balanced and meets . Then either there is a detector in or the following conditions hold: L E M M A 3 . 6 . If a tight set is of size then the (a) strongly crosses , and cut is a shredder. (b) is a two-way -balanced min-cut. Proof: Suppose not. Then is a two-way . Since Proof: Suppose there is no detector in cut preserving and hence . Thus was and each contain a detector, they meet . Now we can not deleted from until iteration , so it should have been invoke the Two-Quarters Lemma to quarters and chosen instead of , contradiction. and conclude that is tight. We claim that . Indeed, otherwise , so by In what follows we assume . The next lemma Lemma 3.7 is a two-way cut, which contradicts shows how (a detection set for shredders) helps to detect Lemma 3.6. Claim proved. two-way min-cuts. This proves (a) and shows that is an L E M M A 3 . 7 . Let be an -balanced two-way min-cut balanced cut. To complete (b), note that is tight by with sides and . Suppose contains a set of size the Two-Quarters Lemma, so by Lemma 3.7 is at least such that is a shredder. Then two-way. contains at least one detector from . Let be an -balanced two-way min-cut with sides Proof: The shredder is -balanced, so it is and . We need to show that meets or both sides weakly detected by . Since is a cut, there are no edges thereof. For the sake of contradiction suppose it is not so. between and , i.e. lies in . It follows that Then without loss of generality , which implies that is connected in , hence lies in a single connected meets every and . Clearly then , for component thereof. Thus at least one detector from is every . Also note that, by Lemma 3.7 cannot contain not in , so it is in . disconnected tight sets larger than . There are three possible cases which we prove separately: Now we are ready to sketch the proof of Thm. 3.3; the 1. does not strongly cross any . details are in the next subsection. 2. strongly crosses exactly one . Proof of Thm. 3.3 (Sketch). Let be an -balanced two3. strongly crosses at least two 's. way min-cut with sides and . We need to show that 1. Cut does not strongly cross any . To re-use meets or both sides thereof. For the sake of contradiction this proof for the second case, we will assume that is only suppose it is not so. Then without loss of generality , -balanced, rather than -balanced, which implies that meets every and . Clearly then Since we assumed that does not strongly cross by , for every . Also note that by Lemma 3.7 Lemma 3.8 we have all 's are disjoint with . Using this cannot contain disconnected tight sets larger than . excises a small a piece of size at There are now three cases to consider, depending on fact we show that each most from , and finally we show that is large, the relation of to the sets . First, suppose does tight, connected, and preserves , and thus algorithm . We show that is not strongly cross any could have made at least one more step. a two-way -balanced cut that was not excluded from .
 ╡ x д   г rеj╒ h i2 ф %  г h 2 g % ш ╡ д   R  8 h 2 % hS ╘ % ╤  2 ╡  h чt 2 q╤ ц ╡  г rn╒ r m! ф  ╥  Rеn{╝ шг ╒ P ╡     h i2 %  Rеn╒ шг ╡   ╥  j|   f 2 ╡  ф    ╡ r    2 %  ┐wlf    ф  h 2 g е% ш  г rеj╒   ╡  

╡ r

C O RO L L A RY 3 . 2 . Each

contains at least one detector.

3.3 Full proof of Thm. 3.3

}

`

г n╒


`


! 4ж

h i2

%

г

╡ x }

╤ 

╡ ╤  #D╟QW ╤ 

╥ R╙ V

. On the other hand, if and suppose then edge to and thus to , so and contradiction.
╤  х fP ╡   ╤ ╟#Wp╟ ╤  ╡ x ╡ ╨|D ╤

then

contains has at least one are not separated, a

large connected subset of such that is a twoway -cut not deleted from , which thus violates the stopping condition.


Y D Ai 1 Ai 2 ... Ait-1 Ait
Xi

Y CD

A1

Y C

D

X1

Bi Ai

A2
(c)

X2

(a)


(b)
╡   ж 2 9 

. We will prove that either there is a leftover part in , which could have used for the next step of the algorithm, or is detected. If is disjoint with then and we are Since (i=1 or 2) strongly crosses , is partitioned immediately done. Otherwise, weakly crosses . by on three non empty parts , (Indeed, is not preserved by , and and . Now, by Lemma 3.8 and our assumption and hence meets both and and so not preserved.) that , we conclude that is tight, But then we satisfy conditions of the Two-Quarters Lemma, and is two-way min-cut. where and is not empty, and thus Consider . We claim that the correspondis tight. Therefore by Lemma 3.7 ing cut is a two-way -cut that preserves is connected and is a two-way cut. This proves the . This contradicts the stopping condition of the algoclaim. rithm: it could have made one more iteration. Therefore it 2. strongly crosses exactly one . Indeed, consider remains to prove the claim. set . By Lemma 3.8 and our assumption that Firstly, is tight by the Two-Quarters Lemma applied there were no detectors in , it has size at least , is to cuts and . Its size is tight and corresponding cut is two-way min-cut. Since , and only one meets (and it does not meet with by our construction), no meets with . Therefore by Lemma 3.8 does not strongly cross any and thus by the case (3.3) is detected by . This so (1) is -balanced, and (2) is connected by lemma proves that there is at least one detector in , and by 3.7 and the assumption that is disjoint with . Since construction , and therefore there is at least , we conclude that (1) is twoone detector in , contradiction. way, since is connected as a union of three 3. strongly crosses at least two 's. We have to non-disjoint connected subsets , and , and (2) is prove that either contains at least one detector from disjoint with by Lemma 3.5. (and thus contradicting our assumption), or we could have To prove that preserves it remains to show that done one more step of the algorithm . Without loss of all 's are disjoint with . Indeed, suppose some meets generality strongly crosses and . (Fig. 4c). . It cannot be properly contained in , hence in .
╡ u T ` ` ` ` D  P ` W `╡  S   n ` ` ` W ╡ r  j  `╡ W S г ╢ е╗H ` ` ` S  ╡    P W  `╡  2 ! Fйж  n ` ` 2 h 2 % ж 8 ` W  ╡ г 2  '╢ д Ё зX г е╛ cu `  u P · aF 9!  ф  ` n|v г ╒ P 2 S `Wy WFW ` P` h i2  Wеj╒ `╡  г 8щ 9 D `╡ % х ∙lf@°|ф P   г  ╢ feH г  ` W S  Dj╒ ` г  YWq `  S  ╜╢ Ё зX 8д S  г  8 mdд  ╜ ` ╡ ╡   xjP ` ` W `╡  '╢ 2 ` W 2  Wn╒ ` г S h i2 ╡  % u  ┐╜ P  P {u ` г ovY P ╡ ╡ x ╡ r'╢  ` D 2 u   ╡ry╜╗yTd╨nEдB    ╡  ╡    P` h2  j щ ╤ Ї  ╡   8 ў 2 t % ╖ ` ф 2t ╤    ` ╤ ╡ x 2t Ї  ╜ b╡  ╡ ╤ BЎYy P ╤   ╡  ╨ Ї  ╡ S  EP   2t ╡ x 2t Ї ╨ ╡ Ї ї╡ ╤ п ` f ╤ 2  d ` f  ╗   jAWuf  `  ` 2t Ї ї╡ Ї  ╡ Ї x ╡ ╤  ╤    ┐w  г n╒ 2t  n| 2t 2t  w╟W ` ` W ╡ ╤ ╤  g╛tP  ╤  P  m 2t   ╤ y  ╤ Ї b╡ Ї b╡   ╤ y  ╧P   ` ╤ B  ` W ╡ # ╤  ф

84

u

S

 '6 cu u P

S

 l╛ 

2

 #nP S

 '6 u

2

 gl

S

 #n 2

u

2

 '6 v1u u P

  
S

 #nP 2

'6 u  S  v 2 S

 ╜ 2

 ╛

and since analogously Lemma we have and thus
 6 

, we have that , and , but by the Two-Quarters and and , and thus

 ╨


S

2

 ╨ P 

 ж

2

 uж

ж╡

2

 dn ╡ 

2

 ег


 ╨

 dj ╡ 

S

 r P 


 ╜|  P

2


 ╨

S


S

 ╨ P  S S

 uж

2

 ег


Suppose we did that, then by its construction is disjoint with any , and thus all 's are disjoint with , , therefore preserves and hence lie in (because is a two-way cut). On the other hand and . So is -balanced two-way mincut and preserves , thus our algorithm could have made one more step, and so we come to contradiction. Now we have to prove our claim. Clearly is tight, connected and is two-way by our definition of and . Suppose the claim holds for , we now prove it for . We have
╡ 8 є F  % h i2 S ц 9uє ┴▐6 u h  2t є F ╤ y ╡ є f  % h2 S є fq є  є   R P ╡ r h ╒д йRA tT u 9u u 9 uє ╡ г еj╒ ц  є F  

First we prove that each of the triples and partition set into the same subsets. Namely, , and . Indeed,

 d

S

 D P 

Figure 4: Three different options of how can interact with the sets portion of between and shrinks to the empty set, and
2  S  2  

in the proof of Theorem 3.3. For (c) we prove the .


4 Extensions and further directions There are a number of natural questions left open by this work. One is to investigate whether an -detection set for node failures of minimum size can be computed in polynomial time for a given graph ; this would parallel the per-instance result we obtain for edge failures. We note that Section 3.1 provides such an optimality result for node failures when the adversary is restricted to deleting a shredder. It would be interesting to extend our results on node failures to obtain bounds for strong detection sets. In fact, our bounds for shredders apply already to strong detection; and in the full version we provide a step in this direction, -detection set for showing it suffices to have a strong some subgraph of of the same connectivity . So without loss of generality we can assume that is minimally -connected. It would clearly be interesting to obtain results on detection sets with respect to adversaries that can delete a number of nodes equal to a constant times the node-connectivity, by analogy with our results for edge-connectivity. To obtain detection set bounds here that are independent of the value of , it is not difficult to see that we need to focus on weak detection; indeed, there exist graphs in which we would need at least nodes in any strong -detection set for node failures. Finally, the problem of deciding whether a given set is an -detection set provides another clear connection to the problem of balanced separators in graphs: indeed, deciding whether the empty set is an -detection set is coNP-complete because of its equivalence to a balanced separator problem. On the other hand, using techniques from [10, 20], we can obtain a polynomial-time algorithm for deciding whether is an -detection set for node failures when ; this is non-trivial due to the fact that there can be exponentially many min-node-cuts. Acknowledgments. It is our pleasure to acknowledge the contribution of Laszlo Lovasz; discussions with him ┤ about the prospect of parameterizing detection sets by the minimum cut size provided a portion of the motivation for this work, and also led to the results described in Section 2.2. References
[1] A. Blumer, A. Ehrenfeucht, D. Haussler and M. Warmuth, "Learnability and the Vapnik-Chervonenkis Dimension," J. of the ACM, 36(4) (1989), pp. 929-965. [2] J. Cheriyan and R. Thurimella, "Fast Algorithms for shredders and -node Connectivity Augmentation," Proc. 28th Annual ACM Symposium on the Theory of Computing, 1996.
√ √  ` W   !жд 4г  ижд йг  !жд Fйзег   ижд г  ижд йзег  ` x ж qг BpG@U P`  ! mи P и  ижд г ! n6и ! !

}


╡ r

So, since proved.

is connected, it meets

, contradiction. Claim

[3] B.Cherkasskij, "Solution of a Problem on Multicommodity Flows in a Network," Ekon. Mat. Metody 13:1(1977), pp. 143151. (in Russian; the result is cited in [9]). [4] F. Chung, M. Garrett, R. Graham and D. Shallcross, "Distance realization problems with applications to Internet tomography," Journal of Computer and System Sciences 63(3): 432-448 (2001). [5] K. Claffy, T. Monk and D. McRobb, "Internet Tomography," Nature, Web Matters, Jan. 7, 1999. [6] E.Dinits, A.Karzanov and M.Lomonosov, "On the Structure of a Family of Minimal Weighted Cuts in a Graph", in A.Fridman, ed., Studies in Discrete Optimization, pp. 290306, Nauka, Moscow, 1976 (in Russian). [7] J.Fakcharoenphol, An improved VC-dimension bound for finding network failures. Master's thesis, Dept. of EECS, UC Berkeley, 2001. Includes a result by A.Gupta. [8] L. Fleischer, "Building Chain and Cactus Representation of all Minimum Cuts from Hao-Orlin in the Same Asymptotic Run Time". J. Algorithms, 33(1) (1999), pp. 51-72. [9] A. Frank, "Packing paths, circuits, and cuts н a survey," in: Paths, Flows and VLSI-Layouts, B. Korte, L. Lovasz, H-J. ┤ Promel, A. Schrijver, eds., Springer-Verlag (1990) pp. 47и 100. [10] H. Gabow, "Centroids, Representations, and Submodular Flows," J. Algorithms 18(1995) pp. 586-628. [11] H. Gabow, "Using expander graphs to find vertex connectivity," Proc. 41st Annual IEEE Symposium on Foundations of Computer Science, 2000. [12] T. Jordan, "On the optimal vertex-connectivity augmenta┤ tion," J. Combin. Theory, Ser. B 63(1) (1995), pp. 8-20. [13] T. Jordan, "On the Number of Shredders," J. Graph Theory, ┤ 31 (1999), pp. 195-200. [14] J. Kleinberg, "Detecting a Network Failure," Proc. 41st Annual IEEE Symposium on Foundations of Computer Science, 2000. [15] L. Lovasz, "On Some Connectivity Properties of Eulerian ┤ Graphs," Acta Math. Hung. 28 (1976), pp. 129-138. и [16] W. Mader, "Uber die Maximalzahl kantendisjunkter AWege," Arch. Math. 30(1978), pp. 325-336. [17] J. Mahdavi and V. Paxson, "IPPM Metrics for Measuring Connectivity," RFC 2678, Network Working Group, Sept. 1999. [18] S. Muthukrishnan, T. Suel and R. Vingralek, "Inferring Tree Topologies Using Flow Tests," Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, 2003. [19] V. Paxson, "Towards a Framework for Defining Internet Performance Metrics," Proc. INET 1996. [20] J.-C. Picard and M.Queyranne, "On the Structure of All Minimum Cuts in a Network and Applications," Mathematical Programming Study 13(1980) pp.8-16.

85