maximum-independent-set

1、296.3:Algorithms in the Real WorldGraph Separators Introduction Applications1296.3Edge Separators783401256An edge separator : a set of edges E E which partitions V into V1 and V2Criteria:|V1|, |V2| balanced|E| is smallV1V2E2296.3Vertex Separators783401256An vertex separator : a set of vertices V V w

2、hich partitions V into V1 and V2Criteria:|V1|, |V2| balanced|V| is smallV1V23296.3Compared with Min-cutstMin-cut: as in the min-cut, max-flow theorem.Min-cut has no balance criteria.Min-cut typically has a source (s) and sink (t).Min-cut tends to find unbalanced cuts. V1V2E4296.3Other namesSometimes

3、 referred to as graph partitioning (probably more common than “graph separators”)graph bisectorsgraph bifurcatorsbalanced or normalized graph cuts5296.3Recursive Separation6296.3Recursive Separation783401256812567340268157430307485185267296.3What graphs have small separators?Planar graphs: O(n1/2) v

4、ertex separators2d meshes, constant genus, excluded minorsAlmost planar graphs:the Internet, power networks, road networksCircuitsneed to be laid out without too many crossingsSocial network graphs:phone-call graphs, link structure of the web, citation graphs, “friends graphs”3d-grids and meshes: O(

5、n2/3)8296.3What graphs dont have small separatorsHypercubes: O(n) edge separators O(n/(log n)1/2) vertex separatorsButterfly networks:O(n/log n) separatorsExpander graphs:Graphs such that for any U V, s.t. |U| a |V|, |neighbors(U)| b |U|. (a 0) random graphs are expanders, with high probabilityIt is

6、 exactly the fact that they dont have small separators that make these graphs useful.9296.3Applications of Separators10296.3Applications of SeparatorsCircuit Layout (from 1960s)VLSI layoutSolving linear systems (nested dissection)n3/2 time for planar graphsPartitioning for parallel algorithmsApproxi

7、mations to NP hard problemsTSP, maximum-independent-setCompact Routing and Shortest-pathsClustering and machine learningMachine visionOut of core algorithmsRegister allocationShortest PathsGraph compressionGraph embeddings11296.3Available SoftwareMETIS: U. MinnesotaPARTY: University of PaderbornCHAC

8、O: Sandia national labsJOSTLE: U. GreenwichSCOTCH: U. BordeauxGNU: PopinetBenchmarks:Graph Partitioning Archive12296.3Different Balance CriteriaBisectors: 50/50Constant fraction cuts: e.g. 1/3, 2/3Trading off cut size for balance (vertex separators):min cut criteria: min quotient separator:All versi

9、ons are NP-hard|E|E|fluxisoperimetricnumberedge= sparsity13296.3Other Variants of Separatorsk-Partitioning:Might be done with recursive partitioning, but direct solution can give better answers. Weighted:Weights on edges (cut size), vertices (balance)Hypergraphs:Each edge can have more than 2 end po

10、intscommon in VLSI circuitsMulticonstraint:Trying to balance different values at the same time.14296.3AsymptoticsIf S is a class of graphs closed under the subgraph relation, thenDefinition: S satisfies an f(n) vertex-separator theorem if there are constants a 0 so that for every GS there exists a v

11、ertex cut set V V, with|V| b f(|G|) cut size|V1| a |G|, |V2| a |G|balanceSimilar definition for edge separators.15296.3Edge vs. Vertex separatorsIf a class of graphs satisfies an f(n) edge-separator theorem then it satisfies an f(n) vertex-separator.The other way is not true (unless degree is bounde

12、d)|E| = n/216296.3Separator Trees7834012568125673402681574303074851852617296.3Separator TreesTheorem: For S satisfying an (a,b) f(n) = n1-e edge- separator theorem, we can generate a perfectly balanced separator with size |C| k b f(|G|).Proof: by picture |C| b n1-e(1 + a + a2 + ) b n1-e(1/1-a)18296.

13、3Algorithms for PartitioningAll are either heuristics or approximationsKernighan-Lin, Fiduccia-Mattheyses (heuristic)Planar graph separators (finds O(n1/2) separators)Geometric separators (finds O(n(d-1)/d) separators in Rd)Spectral (finds O(n(d-1)/d) separators in Rd)Flow/LP-based techniques (give

14、log(n) approximations)Multilevel recursive bisection (heuristic, currently most practical)19296.3Kernighan-Lin HeuristicLocal heuristic for edge-separators based on “hill climbing”. Will most likely end in a local-minima.Two versions:Original K-L: takes n2 time per passFiduccia-Mattheyses: takes lin

15、ear time per pass20296.3High-level description for bothStart with an initial cut that partitions the vertices into two equal size sets V1 and V2Want to swap two equal sized sets X A and Y B to reduce the cut size.Note that finding the optimal subsets X and Y solves the optimal separator problem, so

16、it is NP hard.We want some heuristic that might help.ABYXC21296.3Some TerminologyC(A,B) : the weighted cut between A and BI(v) : the number of edges incident on v that stay within the partitionE(v) : the number of edges incident on v that go to the other partitionD(v) : E(v) - I(v) D(u,v) : D(u) + D

17、(v) - 2 w(u,v)the gain for swapping u and vABCvu22296.3Kernighan-Lin improvement stepKL(G,A0,B0) u A0, v B0 put (u,v) in a PQ based on D(u,v) for k = 1 to |V|/2 (u,v) = max(PQ)(Ak,Bk) = (Ak-1,Bk-1) swap (u,v)delete u and v entries from PQ update D on neighbors (and PQ)select Ak,Bk with best CkNote t

18、hat can take backward steps (“gain” D(u,v) can be negative).ABCvu23296.3Fiduccia-Mattheysess improvement stepFM(G,A0,B0) u A0 put u in PQA based on D(u) v B0 put v in PQB based on D(v) for k = 1 to |V|/2 u = max(PQA)put u on B side and update Dv = max(PQb)put v on A side and update D select Ak,Bk wi

19、th best CkABCvu24296.3Two examples of KL or FMConsider following graphs with initial cut given in red.25296.3A Bad Example for KL or FMConsider following graph with initial cut given in red.KL (or FM) will start on one side of the grid (e.g. the blue pair) and flip pairs over moving across the grid

20、until the whole thing is flipped.After one round the graph will look identical?222111226296.3Boundary Kernighan-Lin (or FM)Instead of putting all pairs (u,v) in Q (or all u and v in Q for FM), just consider the boundary vertices (i.e. vertices adjacent to a vertex in the other partition).Note that v

21、ertices might not originally be boundaries but become boundaries.In practice for reasonable initial cuts this can speed up KL by a large factor, but wont necessarily find the same solution as KL.27296.3Performance in PracticeIn general the algorithms do very well at smoothing a cut that is approxima

22、tely correct.Works best for graphs with reasonably high degree.Used by most separator packages eitherto smooth final resultsto smooth partial results during the algorithm28296.3Separators OutlineIntroduction: Algorithms:Kernighan LinBFS and PFSMultilevelSpectral29296.3Breadth-First Search Separators

23、123456Run BFS and as soon as you have included half the vertices return that as the partition.Wont necessarily be 50/50, but can arbitrarily split vertices in middle level.Used as substep in Lipton-Tarjan planar separators.In practiced does not work well on its own.30296.3Picking the Start VertexTry

24、 a few random starts and select best partition foundStart at an “extreme” point. Do an initial DFS starting at any point and select a vertex from the last level to start with.If multiple extreme points, try a few of them. 31296.3Priority-First Search Separators1169710834521Prioritize the vertices ba

25、sed on their gain (as defined in KL) with the current set.Search until you have half the vertices.32296.3Multilevel Graph PartitioningSuggested by many researchers around the same time (early 1990s).Packages that use it:METISJostleTSL (GNU)ChacoBest packages in practice (for now), but not yet proper

26、ly analyzed in terms of theory.Mostly applied to edge separators.33296.3High-Level Algorithm OutlineMultilevelPartition(G)If G is small, do something brute forceElseCoarsen the graph into G (Coarsen)A,B = MultilevelPartition(G)Expand graph back to G and project thepartitions A and B onto A and BRefi

27、ne the partition A,B and return resultMany choices on how to do underlined parts34296.3MGP as Bubble DiagramGCoarsenExpand, Projectand Refine“Brute Force”35296.3How to CoarsenGoal is to pick a sample G such that when we find its partition it will help us find the partition of G.Possibilities?36296.3

28、Random SamplingPick a random subset of the vertices.Remove the unchosen vertices and their incident edges37296.3Random SamplingPick a random subset of the vertices.Remove the unchosen vertices and their incident edgesGraph falls apart if it is not dense enough.38296.3Maximal MatchingsA maximal match

29、ing is a pairing of neighbors so that no unpaired vertex can be paired with an unpaired neighbor.The idea is to contract pairs into a single vertex.39296.3A Maximal MatchingCan be found in linear time greedily.40296.3A side noteCompared to a maximum matching: a pairing such that the number of covere

30、d nodes is maximum41296.3Coarsening42296.3Collapsing and WeightsNew vertices become weighted by sum of weights of their pair.New edges (u,v) become weighted by sum of weights of multiple edges (u,v) We therefore have to solve the weighted problem.1221Why care about weights?43296.3Heuristics for find

31、ing the MatchingRandom : randomly select edges.Prioritized: the edges are prioritized by weight.Visit vertices in random order, but pick highest priority edge first.Heaviest first: Why might this be a good heuristic?Lightest first: Why might this be a good heuristic?Highly connected components: (or

32、heavy clique matching). Looks not only at two vertices but the connectivity of their own structure.44296.3Finding the Cut on the Coarsened Graph45296.3Exanding and “Projecting”46296.3e.g. by using Kernighan-LinRefining47296.3After Refinement48296.3METISCoarsening: “Heavy Edge” maximal matching.Base

33、case: Priority-first search based on gain. Randomly select 4 starting points and pick best cut.Smoothing: Boundary Kernighan-LinHas many other options. e.g., Multiway separators.49296.3Separators OutlineIntroduction: Algorithms:Kernighan LinBFS and PFSMultilevelSpectral50296.3Spectral SeparatorsBase

34、d on the second eigenvector of the “Laplacian” matrix for the graph.Let A be the adjacency matrix for G.Let D be a diagonal matrix with degree of each vertex.The Laplacian matrix is defined as L = D-A51296.3Laplacian Matrix: ExampleNote that each row sums to 0.3124552296.3Fiedler VectorsEigenvalues

35、l1 l2 l3 . ln, real, non-negative.Find eigenvector corresponding to the second smallest eigenvalue: L x2 = l2 x2This is called the Fiedler vector.What is true about the first eigenvector?53296.3Modes of Vibration(Picture from Jim Demmels CS267 course at Berkeley.)x254296.3Fiedler Vector: ExampleNote

36、 that each row sums to 0.If graph is not connected, what is the second eigenvalue?3124555296.3Finding the SeparatorSort Fiedler vector by value, and split in half.31245sorted vertices: 3, 1, 4, 5, 256296.3Power MethodIterative method for finding first few eigenvectors.Every vector is a linear combination of its eigenvectors e1, e2, Consider: p0 = a1 e1 + a2 e2 + Iterating pi+1 = Api until it settles will give the principal eigenvector (larg