Distributed Graph Algorithms and Local Problems in Spring 2023

Distributed Graph Algorithms Spring 2023 Class 3: Local Problems & Tree Coloring

The LOCAL Model (Linial, FOCS 87) ? nodes with unique identifiers 8 5 Initially each node knows: Its ID Estimate on global parameters: E.g., number of nodes, max-degree, etc. 7 3 2 Synchronous rounds: 1. Each node/computer does some internal computation 2. Send a message to each neighbor (possibly unbounded) 3. Receive message from each neighbor Unbounded internal computation & message size

Slide by Fabian Kuhn The LOCAL Model The LOCAL Model ? Trivial upper bound: ?(???? ? ) rounds ?-Round Algorithm: Each node computes its output as a function of the initial state of its ?-neighborhood 3

Slides by Fabian Kuhn Local Graph Algorithms Objective: solve some graph problem on the network graph 12 15 9 20 21 1 8 4 11 3 16 2 17 5 At the start: Each node knows its own ID and nothing else about the topology At the end: Each node knows its part of the output (e.g., its color) Local checkability We consider graph problems where the solution can be checked locally (e.g., ?(1)-radius ball) e.g., a node can locally check whether it has a different color than its neighbors [Naor,Stockmeyer; STOC 93], [Fraigniaud,Korman,Peleg; FOCS 11] 4

Slide by Fabian Kuhn LOCAL Problems (Examples) LOCAL Problems (Examples) ? + ? -Vertex Coloring Objective: properly color the nodes with + 1 colors : maximum degree + 1 colors: what a simple sequential greedy algorithm achieves 5

Slide by Fabian Kuhn LOCAL Problems (Examples) LOCAL Problems (Examples) Maximal Independent Set (MIS) Objective: compute a maximal independent set (MIS) Non-extendible set of pairwise non-adjacent nodes Trivial to compute sequentially 6

Slide by Fabian Kuhn LOCAL Problems (Examples) LOCAL Problems (Examples) Maximal Matching Objective: compute a maximal matching Non-extendible set of pairwise non-adjacent edges A maximal matching is an MIS of the line graph 7

Challenges in the LOCAL Model Slide by Fabian Kuhn Symmetry Breaking / Local Coordination ? ? Neighboring / nearby nodes need to output different values e.g., different colors, at most one can be in an MIS, etc. Nodes need to decide in parallel Key Challenge: locally coordinate among nearby nodes randomization naturally helps (e.g., choose color at random) 8

Next: Coloring Trees with 3 Colors! Next: Coloring Trees with 3 Colors!

Coloring Rooted Trees Observation: Every tree can be colored with two colors Lower Bound [Linial, 89]: Any algorithm that colors an ?-vertex path with two colors requires ?(?)rounds 0 0 iff ?(?,?)is even ? ?

Coloring Rooted Trees with Three Colors Theorem 1 [Cole, Vishkin 86] : Every rooted tree can be colored with three colors using ?(??? ?) rounds ??? ? = min{? log?? 2} Iterated log-function: log(1)? = log ? log(2)? = loglog ? log(?+1)? = log(log??)

Lower Bounds for 3-Coloring Theorem 2 [Linial 89] : Any algorithm that 3-colors an ?-vertex oriented path requires ?(??? ?) rounds Simplified proof by [Laurinharju and Suomela 2014] Next: coloring rooted trees with 6 colors in ?(??? ?) rounds

Six-Coloring in ?(log?) Rounds Initially set ? ? = ?? ? Legal coloring with ?(????) bits [000100001] Goal: In single round, re-color vertices with ? loglog ? -bit colors [011100001] ?(??? ?)repetitions ?(?)-bit coloring

Six-Coloring Algorithm Root ? assigns ??= ? [00000000] Code for a non-root vertex ?: 1. Set ??= ??? and send to children 2. Repeat: [00101110] [00101110] (2.1) ? = ???{ ? ??? ?? ?(?)} (2.2) ??= ?,??? (2.3) Send ?? to children

Six-Coloring Algorithm Root ? assigns ??= ? ? [00000000] Code for a non-root vertex ?: 1. Set ??= ??? and send to children 2. Repeat: ? [10101110] ? (2.1) ? = ???{ ? ??? ?? ?(?)} [00101110] (2.2) ??= ?,??? (2.3) Send ?? to children Run by all nodes in parallel ??= [0011] ??= [1110]

Analysis ? ? [10101110] Correctness: In each iteration, the algorithm produces a legal coloring. ? [00101110] Proof: Consider ? and ? = ?(?). Let??,??be the indices chosen by ?,? Case 1: ?? ?? Code for a vertex ?: (2.1) ? = ???{ ? ??? ?? ?(?)} Case 2: ??= ?? (2.2) ??= ?,??? ???? ???? = ??(??)

Analysis Runtime: Within ?(??? ?)iterations, the final coloring consists of 6 colors Proof Sketch: ?? number of bits in colors after the ?th iteration ?0= log ? ?1= loglogn + 1 ?2= log k1 + 1 Observation: ??+?< ?? as long as ?? ? Once ??= ?we get 6 colors!

Reducing to Three Colors Procedure Shift-Down: 1. Each vertex adopts color of its parent 2. Root picks a free color in ?,?,? 1 0 Shift-Down 0 0 0 4 5 3 Sibling are mono-chromatic! 5 5 3 4 2 3 2 5 2 2 3 4 2 2 2 0 4 5 3 3 3 3 2 4 4 1

Reducing to Three Colors Idea: Cancel colors {3,4,5} on by one by applying Shift-Down From Six to Three Colors: For ? ?,?,?do: 1. Apply Shift-Down 2. Each vertex with color ? picks a free color in {?,?,?} Is this safe? Is this possible?

Example: Cancelling Color 5 1 1 0 Shift- Down 0 0 0 0 0 0 Cancel 5 4 5 3 5 5 1 3 4 1 3 4 2 3 2 5 2 2 2 2 3 4 2 2 2 2 2 2 0 4 5 3 3 3 3 3 3 3 3 2 4 4 1

Coloring Unoriented Trees Linial 92: Coloring a balanced ?-regular unoriented tree with less than ?/? colors requires ? log ?rounds. log ?

Many Variants of Vertex Coloring (? + ?)Coloring: Goal: Each vertex ? outputs ?? {?, ,?} (? + ?) List-Coloring: Each vertex ? has a palette ???(?)of ? + ? colors chosen from {?, ,????(?)} Goal: outputs ?? ???(?) (??? + ?)Coloring: Goal: Each vertex ? outputs ?? {?, ,???(?)}

( + 1) Coloring: State-of-the-Art Randomized complexity [Chung, Li, Pettie 2018]: ?(log3log?) rounds Deterministic complexity [Ghaffari and Kuhn, 2021]: ?(log2? log ) rounds Lower bounds: (log ?) rounds (by Linial 1989)! Some good news: ? + ? ? coloring in ??/?(??? ?) rounds (using randomization)