Overall minimum cutThe ProblemExampleExampleImmediate SolutionTime for Min-CutImprovementRandomized SolutionMeaning of “contraction”Example:Example:Example:Example:Example:Is output min-cut?Is output min-cut?Is output min-cut?Is output min-cut?When is C a min-cut?Probability calculationProbability calculationProbability calculationProbability calculationProbability calculationProbability calculationThe Contraction AlgorithmSlide 27Slide 28ExercisesolutionAlgorithm 2 for min cutsSlide 32Slide 33Slide 34Slide 35Slide 36Most Tightly Connected VertexThe AlgorithmExampleExampleExampleExampleThe AlgorithmThe AlgorithmMerge(G,e,f)ExampleThe AlgorithmExampleExampleExampleExampleExampleExampleExampleExampleExampleExampleSlide 66Theorem -2 (Harary)Theorem -2 (Harary)a. Harary Proof – such a graph can be constructeda. Harary Proof – such a graph can be constructedExerciseOverall minimum cut•The minimum cut between two specified nodes can be obtained as a byproduct of the maximum flow computation. If, however, we want an overall minimum cut in the whole graph, then a single maximum flow computation does not suffice. Interestingly, one can find an overall minimum cut directly, without using anything about maximum flows. Below we present two relaitvely simple algorithms.The ProblemINPUT: Undirected Graph G=(V,E)OUTPUT: A smallest-size set of edges such that G’=(V,E-E1) is not connected.EE 1ExampleACBDGEFExampleACBDGEFE1 = BEImmediate SolutionFor every pair of nodes s,t find the min-cut Ms,t Choose the pair <s,t> with the smallest Ms,t.Time= O(n² T(min-cut) )Time for Min-CutFord-Fulkerson: O(|E|flow)In our case: max flow ≤ nso: O(n² |E|n) = O(n² n³)This can be improvedImprovementWe don’t need all pairs.Why?Every node is in one side of a cut.Therefore: Fix node s. Try all other n-1 options as node t.Time: )(4nORandomized SolutionRepeat Until 2 nodes left:1. choose edge at random2. “contract” edgeWhen only 2 node left:Take all edges between them as the min-cut.Time: O(|E|)=O(n²)Meaning of “contraction”Make edge ab with its two adjacent nodes a,b into a single node ab.All edges of a and b will now be edges from ab (creating a multigraph).Example:ACBDGEFExample:ACBDGEFcontractExample:ACBDGEFcontractACBDEFGExample:ACBDGEFcontractACBDEFGcontractExample:ACBDGEFcontractACBDEFGcontractACB EFGDIs output min-cut?Not necessarily.Is it a cut?-yes.Is output min-cut?Not necessarily.Is it a cut?-yes.Could there be an edge between these sides that was deleted?Is output min-cut?Not necessarily.Is it a cut?-yes.No. The only deleted edges were within the contractions.Is output min-cut?Not necessarily.Is it a cut?-yes. cut C={e1,…,ec}No. The only deleted edges were within the contractions.When is C a min-cut?When none of the edges in C={e1,…,ec}are chosen to be contracted.What is the probability of that happening?Probability calculationNote: We can assume that degree of every node in graph throughout contraction process ≥ cProbability calculationNote: We can assume that degree of every node in graph throughout contraction process ≥ cOtherwise:Cut node and get cut of size < c.Probability calculationProbability that one of the C edges is chosen at first stage:Probability that one of the C edges is chosen after stage i ≤:Probability of not choosing an edge of C at stage i ≥: nnccEc22/incinc22/)(ininin 221Probability calculationNote: The algorithm has n-2 stages (at that point 2 nodes are left).Probability of not choosing an edge from C at any stage ≥ =)1)(1)(1()1)(1)(1)(1()3(2)4(2)5(23222122nnnnnnnnnn))()(())()()((3142533524132nnnnnnnnProbability calculationWhat do we have?))()(())()()((3142533524132nnnnnnnnProbability calculationWhat do we have?Telescope cancellations:=))()(())()()((3142533524132nnnnnnnn))()(())()()((3142533524132nnnnnnnn)(21)1(2nOnnThe Contraction Algorithm•Probability that smallest cut is not chosen is (1-1/n2)•Therefore, if we repeat the algorithm K times independently and choose the smallest of the found cuts, say C, then the following holds:Pr(C is not a minimum cut) ≤ ••If K is chosen as K = ln2, then the above probability will be approximately e-l, which is very small already for moderate values of l.•If l = 10, e-10 <.001•An interesting by-product of this algorithm is the theorem that the number of minimum cuts in a graph is at most n2, since each arises with at least 1/n2 probability in a run and these are mutually exclusive events. Note that the total number of different cuts may well be exponentially large, but only at most n2 of them can be minimum (actually, n2 is only an upper bound, the precise tight bound is n(n - 1)/2).Exercise•Give an example to show that the bound n(n - 1)/2 on the number of minimum cuts is tight (that is, it can hold with equality).solution•Consider a graph on n nodes which is a simple circle (ring). •It cannot be disconnected by removing a single edge, but it can be disconnected by removing 2 edges, so the minimum cut size is 2. •If we remove any 2 edges from the graph, it gets disconnected. Therefore, every pair of edges form a minimum cut. •Since there are n edges in a circle on n nodes, we can choose n(n-1)/2 different minimum cuts, which is exactly the bound on the number of minimum cuts. •Thus, in this case the bound holds with equality, which shows that it is tight.Algorithm 2 for min cuts•A Deterministic Algorithm for Minimum Cut: The Nagamochi-Ibaraki Algorithm•A simple deterministic algorithm for minimum cuts was discovered by Japanese researchers Nagamochi and Ibaraki. Recall that the (edge-)connectivity of a graph G is denoted by λ(G); and λ(x,y) denotes the connectivity between two different nodes x, y.•Let Gxy be the graph obtained from G by contracting (merging) nodes x, y.•In this operation we omit the possibly arising loop (if x, y are connected in G), but keep the parallel edges.•We can now use the following result:For any two nodes x, yλ(G) = min{ λ(x, y), λ(Gxy) } (1)•Thus, if we can find two nodes x, y for which λ(x, y) can be computed easily (without a flow computation), then the above formula yields a simple recursive algorithm.•One can indeed easily find such a pair x,y of nodes. This is done via the
View Full Document
Unlocking...