Report

Routing in Undirected Graphs with Constant Congestion Julia Chuzhoy Toyota Technological Institute at Chicago Routing Problems Input: Graph G, source-sink pairs (s1,t1),…,(sk,tk). Goal: Route as many pairs as possible; minimize edge congestion. Routing Problems Input: Graph G, source-sink pairs (s1,t1),…,(sk,tk). Goal: Route as many pairs as possible; minimize edge congestion. Routing Problems Input: Graph G, source-sink pairs (s1,t1),…,(sk,tk). Goal: Route as many pairs as possible; minimize edge congestion. Edge congestion: 2 Routing Problems Input: Graph G, source-sink pairs (s1,t1),…,(sk,tk). Goal: Route as many pairs as possible; minimize edge congestion. n – number of graph vertices k – number of demand pairs terminals – vertices participating in the demand pairs Routing Problems Input: Graph G, source-sink pairs (s1,t1),…,(sk,tk). Goal: Route as many pairs as possible; minimize edge congestion. • 3 pairs with congestion 2 Routing Problems Input: Graph G, source-sink pairs (s1,t1),…,(sk,tk). Goal: Route as many pairs as possible; minimize edge congestion. • 3 pairs with congestion 2 • 2 pairs with congestion 1 Edge Disjoint Paths (EDP) Congestion Minimization Route maximum number of pairs on edge-disjoint paths Route all pairs; minimize congestion Congestion Minimization Route all pairs; minimize congestion • -approximation [Raghavan, Thompson ‘87] • -hard to approximate [Andrews, Zhang ‘07] Edge Disjoint Paths (EDP) Route maximum number of pairs on edge-disjoint paths • When k is constant, can be solved efficiently [Robertson, Seymour ‘90] • NP-hard in general [Karp ’72] • -approximation algorithm [Chekuri, Khanna, Shepherd ’06]. Best possible? – LP-relaxation: maximum multicommodity flow between the demand pairs with no congestion. – Integrality gap: [Chekuri, Khanna, Shepherd ‘06] Edge Disjoint Paths (EDP) Route maximum number of pairs on edge-disjoint paths • When k is constant, can be solved efficiently [Robertson, Seymour ‘90] • NP-hard in general [Karp ’72] • -approximation algorithm [Chekuri, Khanna, Shepherd ’06]. • When global min-cut is , there is a polylog(n) approximation [Rao, Zhou ‘06] • -hardness of approximation for any [Andrews, Zhang ‘05], [Andrews, C, Guruswami, Khanna, Talwar, Zhang ’10] Special Cases Expander graphs In a strong enough constant-degree expander, any demand set on vertices can be routed on edge-disjoint paths [Frieze ‘00] Planar graphs, Trees… Edge Disjoint Paths (EDP) Congestion Minimization Route maximum number of pairs on edge-disjoint paths Route all pairs; minimize congestion • -approximation • matching integrality gap • • • -hardness -approximation -hardness EDP with Congestion (EDPwC) A factor- approximation algorithm with congestion c routes . demand pairs with congestion at most c. optimum number of pairs with no congestion allowed EDPwC • Congestion : constant approximation [Raghavan, Thompson ‘87] • -approximation with congestion c [Azar, Regev ’01], [Baveja, Srinivasan ’00], [Kolliopoulos, Stein ‘04] • polylog(n)-approximation with congestion poly(log log n) [Andrews ‘10] Today: polylog(k)-approximation with congestion 14. • -hardness for any c [Andrews, C, Guruswami, Khanna, Talwar, Zhang ’10] Edge Disjoint Paths (EDP) Congestion Minimization Route maximum number of pairs on edge-disjoint paths Route all pairs; minimize congestion • -approximation • matching integrality gap • • • -hardness -approximation -hardness EDP with Congestion (EDPwC) • polylog(k)-approximation with congestion 14 • -hardness with congestion c Well-Linkedness [Robertson,Seymour], [Chekuri, Khanna, Shepherd], [Raecke] Well-Linkedness Graph G is -well-linked for the set T of terminals, iff for any partition (A,B) of V(G), Well-Linkedness Set S is -well-linked iff for any partition (A,B) of S, Normally out(S) Any matching on the edges of out(S) can be fractionally routed inside S with congestion Pre-Processing Input: Graph G, source-sink pairs (s1,t1),…,(sk,tk). Theorem [Chekuri, Khanna Shepherd ‘04] Can efficiently partition G into disjoint subgraphs G1,…,w.l.o.g. Gr, suchthat that: Can assume G is well-linked for terminals Gi the • For each inducedthe sub-problem terminals are well-linked • Total fractional solution value for all induced sub-problems is High-Level Plan [CKS ‘04] 1. Embed an expander on a subset of terminals into G. Crossbar – expander vertices – expander edges terminals paths in G 2. Route a subset of the demand pairs in the Embedding congestion: max load on any edge of G expander Goal Embed an expander over a subset of terminals into G. • Include polylog(k)-fraction of the terminals • Constant congestion Cut-Matching Game [Khandekar, Rao, Vazirani ’06] Cut Player: wants to build an expander Matching Player: wants to delay its construction There is a strategy for cut player, s.t. after O(log2n) iterations, we get an expander! Embedding Expander into Graph Embedding Expander into Graph After O(log2k) iterations, we get an expander embedded into G. Problem: congestion Ω(log2k) Solution? Idea [Rao Zhou ‘06]: • Split G into graphs G1,…,Gh – – – – V(Gi)=V(G) for all i Every edge of G belongs to at most one Gi Each Gi well-linked for the terminals h=O(log2k) • Run the cut-matching game. Use Gi to route flow in iteration i. Problem: Can only do it if min-cut in G is Ω(log5n) • [Andrews ‘10] adapted this to general graphs, with congestion poly(log log n) Getting a Constant Congestion Starting Point Input: Graph G, source-sink pairs (s1,t1),…,(sk,tk). G is well-linked for the terminals. Goal: Route OPT/polylog(k) demand pairs with constant congestion. Embedding an Expander into G Expander vertex connected component in G containing the terminal Expander edge path connecting some pair of vertices in the two components An edge of G may only belong to a constant number of the components/paths. Embedding an Expander into G Routing on vertex-disjoint paths in X gives a good routing in G! Embedding an Expander into G Expander vertex connected component in G containing the terminal Expander edge path connecting some pair of vertices in the two components An edge of G may only belong to a constant number of the components/paths. Embedding an Expander into G Families of Good Vertex Sets Good Vertex Subset S is a good vertex subset iff: • S contains no terminals • S is well-linked • There are k/polylog k paths connecting out(S) to the terminals, with congestion polylog k. Family of Good Vertex Subsets Ω(log2k) disjoint good vertex subsets. • Each subset can send k/(polylog k) flow units to the terminals • total congestion polylog k Rest of the proof 1. We can find a good family of subsets. 2. Given a good family of subsets, we can embed an expander into G. Rest of the proof 1. We can find a good family of subsets. 2. Given a good family of subsets, we can embed an expander into G. Want: • k/polylog k trees • every edge of G participates in a constant number of trees • Each tree Ti spans a distinct terminal ti and a distinct edge eij in out(Sj) for each j. Want: • k/polylog k trees • every edge of G participates in a constant number of trees • Each tree Ti spans a distinct terminal ti and a distinct edge eij in out(Sj) for each j. • Edge eij is viewed as a copy of ti for set Sj. Embedding an Expander Embedding an Expander Expander vertex the tree spanning the terminal Expander edges: via the cut-matching game of [KRV] Embedding an Expander Embedding an Expander After O(log2k) iterations, we obtain an expander embedded into G.… Grouping Technique [CKS] - well-linked - selected edges • is very well-linked Any partition of into equal-sized subsets can be integrally routed with congestion 2. • . Embedding an Expander After O(log2k) iterations, we obtain an expander embedded into G.… Rest of the proof 1. We can find a good family of subsets. 2. Given a good family of subsets, we can embed an expander into G. Rest of the proof 1. We can find a good family of subsets. 2. Given a good family of subsets, we can embed an expander into G. Contracted Graphs contract Only contract clusters C where • C is well-linked • Does not contain terminals • |out(C)|<k/polylog(k) Good contracted graph Finding a Good Vertex Subset • Start with G. • In every iteration: – either find a good vertex subset – or find a good contracted graph with fewer edges Iteration Description |E(A)|≥|out(A)|/4 uncontract Iteration Description well-linked decomposition |E(A)|≥|out(A)|/4 Well-linked Decomposition [Chekuri, Khanna, Shepherd], [Raecke] • New clusters are well-linked • … Iteration Description well-linked decomposition |E(A)|≥|out(A)|/4 now |E(A)|<<|out(A)| Problem: for some cluster C, |out(C)| may be too large contract Iteration Description C C is a good cluster? • Well-linked Iteration Description C C is a good cluster? Well-linked • Can route k/polylog(k) flow units to the terminals? C is a good set! A small cut separates C from the terminals Iteration Description uncontract good contracted graph with fewer edges! contract well-linked decomposition Finding a Good Vertex Subset Random subset A of vertices Uncontract + Well-linked decomposition All clusters have small outdegree? yes smaller contracted graph no Good vertex subset? no yes uncontract + WLD+contract done! smaller contracted graph Algorithm for EDPwC Find a good family of vertex subsets Embed an expander into G Find vertex-disjoint routing on the expander Transform into routing in G Summary • We obtain a polylog(k)-approximation for EDPwC with congestion 14. • Smaller congestion? • Congestion minimization? Thank you!