Randomized Algorithms for Cuts and Colouring in Distributed Computation

Randomized Algorithms for Cuts and Colouring David Pritchard, NSERC Post-doctoral Fellow

What Can Randomness Do? Part 1: Check 3-edge-connectivity in a distributed network Joint with Ramakrishna Thurimella (Denver) Part 2: Find many disjoint set covers as a function of min degree Joint w/ B la Bollob s (Cambridge & Memphis), Thomas Rothvo (MIT), Alex Scott (Oxford)

Distributed Computation Vertices are computers that communicate using edges initially, local/no knowledge goal: compute global graph property

Distributed Computation Message passing happens in rounds time complexity: # rounds elapsed Diameter := maximum distance (# hops) between two nodes e.g., Diam = 5

Distributed Computation Message passing happens in rounds time complexity: # rounds elapsed Diameter := maximum distance (# hops) between two nodes if message lengths are unrestricted, we can compute anything in O(Diameter) rounds CONGEST model: limit message lengths to O(log |V|) bits

Known Time Complexities Synchronizer w/polylog overhead, AP 90 Breadth-first spanning tree: O(Diam) time Universally optimal

Known Time Complexities Synchronizer w/polylog overhead, AP 90 Breadth-first spanning tree: O(Diam) time Universally optimal Depth-first spanning tree: O(|V|) time; no good lower bound Min-cost spanning tree (KP 98, PR 99): O( V log*V + Diam), ( V/log V)

Main Result Distributed algorithm to check 3-edge- connectivity in O(Diam) time explicit: finds 2-edge-cuts application: reinforcement beats prior O(Diam+V2); optimal Main tool: sample cycle space randomly

Main Tool: Cycle Space connected network/graph (V, E) (V, F) Eulerian if v, degF(v) is even Cycle space := the vector space {F : (V, F) is Eulerian} notation abuse: F is a subset of E and also its characteristic vector {0, 1}E why is it a vector space? even deg. even deg. even deg. =

Random Sampling Claim: if T is a spanning tree, any 0-1 vector on E\T extends uniquely to an Eulerian subgraph F thick: T green: in F red: not in F grey: undecided Corollary: sampling from the cycle space uniformly is as easy as sampling 2E\T

Cuts and Cycles Claim. | (S) F| is even for all Eulerian F use Euler tour(s)! Claim. Unless E = (S) for some S, for a random F from the cycle space, |E F| is even exactly of the time.

Finding 2-Edge Cuts? 2 edges {e, e } form a cut |{e, e } F| even for all Eulerian F e and e always both or neither in F Implies transitivity: if {e, f} and {f, g} are 2-edge cuts, so is {e, g} Call equivalence classes cut classes cut class some edges not in any 2-edge-cuts

Algorithm for 2-Edge Cuts Set k = O(log |V|). Sample F1, F2, Fk from cycle space. Group equal rows and output them as cut classes. {ei, ej} is a 2-edge-cut ei, ej have equal rows, with error probability 2-k Pr[any error] |E|22-k = 1/poly(V) F1 F2 F3 F4 F5 F6 1 0 1 1 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 e1 e2 e3 e4 e5 1 0 1 1 0

Questions Leads to O(Diam + /log V)-time algorithm for cut vertices O(Diam + V log*V) known before (Thurimella 97) Is O(Diam) possible or not? Can this be derandomized? in a distributed way?

Festival Scheduling Set V of musicians, list of bands V A schedule maps each band to a day Each musician must play every day What is max # days in schedule?

The Basic Question Input: A set system/hypergraph (V, H) each S H is a hyperedge S V A cover-decomposition is a partition H = H1 H2 Hk s.t. each Hi covers V, i.e. {S | S Hi} = V equivalently, a polychromatic coloring goal: maximize #parts/#colours

cd: Cover-Decomposition Number cd(H) largest k for which there is a cover-decomposition into k parts Easy: cd minimum degree Does a converse hold? If 100 (H covers every point 100 times), can we get many disjoint covers? In general, no: cd = 1 is still possible But for specific families

Cover-Decomposition in Graphs R. P. Gupta, 1970s: In a graph, cd -1. In a multigraph, cd 3 +1/4 . Tight multigraph examples: =2 cd=1 =3 cd=2 =4 cd=3

Cover-Decomposition in Geometry Ground set = finite X Rd, edges = subsets of X covered by shapes

Cover-Decomposition in Geometry cd = ( ) Translates of any convex polygon Axis-aligned strips Axis-aligned rectangles Halfspaces in 2D 3D orthants not cover-decomposable Translates of any non- convex quadrilateral Conjecture [Pach, 1980]: for any fixed convex set S, there is S, so that hypergraphs with a finite ground set in R2 and translates of S as edges, with S, have cd(H) 2. The family is cover-decomposable. Unit strips in 2D 4D orthants

Our Results Hypergraphs with bounded edge size R cd /log R; Techniques: LLL, discrepancy, LPs Hypergraphs of paths in trees cd /5 hypergraph families as possible. this is tight Goal: find out how cover-decomposition number (cd) depends on minimum degree ( ) in as many natural Hypergraphs of VC-dimension D cover-decomposable only for D = 1

/ Lovasz Local Lemma: There are any number of bad events, but each is independent of all but D others. LLL: If each bad event has individual probability at most 1/eD, then Pr[no bad events happen] > 0. Natural to try in our setting: randomly k-colour the edges

Edge size R Pick some k, randomly k-colour edges. bad event: vertex v misses colour c. Dependence degree k R (max degree) set all degrees to by shrinking Analyze: Pr[v misses c] (1-1/k) e- /k Need Rk e- /k < 1/e dependency degree cd ( /(log R + log )) v S S\{v}

Splitting the Hypergraph ( /log R ) is already ( /log R) if poly(R) Idea: partition edges to H1,H2, ,HM with (Hi) poly(R), (Hi) ~ (H)/M ( (Hi)/log R) covers = ( (H)/M/log R) covers ( (H)/M/log R) covers ( (H)/M/log R) covers M=3 ~ /log R covers

Iterated Pairwise Splitting Split H into H+, H- so that v, : deg(v, H ) deg(v, H)/2 - Equivalent view: assign 1 to edges, s.t. |total weight on each vertex| 2 discrepancy! Beck-Fiala 1981: there is an assignment with discrepancy 2R

Beck-Fiala Algorithm LP variables: S: 0 xS = 1 - yS 1 v: S:v S xS /2, S:v S yS /2 1. find extreme point LP solution 2. fix variables with values 0 or 1 3. discard all constraints involving R non-fixed variables Termination lemma |Hnonfixed|; each var is in R constraints basis of tight degree constraints has size

Remarks Maximum edge size R: use better discrepancy bound to get right multiplicative constant Concentration/LLL instead of B-F cd /5 for paths in trees: B-F, different termination lemma linear independence of basis

Sparse Hypergraphs [Alon-Berke-Buchin2-Csorba-Shannigrahi-Speckmann-Zumstein] ( , )-sparse hypergraph := incidences(U V, F H) |U|+ |F| : -vertex-sparse incidences -edge-sparse incidences idea: shrink off -edge-sparse ones, obtaining cd ( - )/log bipartite incidence graph vertices hyperedges

Cover Scheduling Hyperedges are sensors monitoring V Each hyperedge S has battery life dS Goal: schedule when each should turn on, so V is covered from time 0 to T How large can T be? (Cover-decomposition: d 1) Result: (min point coverage/R) schedule is possible Open Q: improve R to log R!