PaperlayerView exact revision on arXiv

Source-linked AI summary

Local Conflict Coloring

Pierre Fraigniaud, Marc Heinrich, Adrian Kosowski

arXiv:1511.01287v2cs.DScs.DC

TL;DR

Which locally checkable tasks admit deterministic sublinear-in-∆ round complexity, including the previously more challenging (∆+1)-list-coloring problem? The paper represents tasks as conflict coloring, with candidate-color lists at nodes and forbidden color pairs on edges, and applies iterative simplification to solve them. For l/d > ∆, the paper reports improved deterministic round complexities for conflict coloring, (∆+1)-coloring, and several coloring variants.

  • Problem

    Which locally checkable tasks admit deterministic sublinear-in-∆ round complexity, including the previously more challenging (∆+1)-list-coloring problem?

    Source: §1.1 · p. 3

  • Method

    The paper represents tasks as conflict coloring, with candidate-color lists at nodes and forbidden color pairs on edges, and applies iterative simplification to solve them.

    Source: §1.2 · p. 4

  • Results

    For l/d > ∆, the paper reports improved deterministic round complexities for conflict coloring, (∆+1)-coloring, and several coloring variants.

    Source: §6 · p. 15

  • Takeaways & Limitations

    The algorithm solves most classical coloring variants, including (2∆−1)-edge-coloring, (∆+1)-list-coloring, and sufficiently large-palette forbidden color-distance coloring.

    Source: §1.2 · p. 4

    The generic algorithm requires l/d > ∆; the authors know no MIS or maximal-matching instantiations meeting this threshold.

    Source: §1.2 · p. 4

Abstract

from arXiv · show

Locally finding a solution to symmetry-breaking tasks such as vertex-coloring, edge-coloring, maximal matching, maximal independent set, etc., is a long-standing challenge in distributed network computing. More recently, it has also become a challenge in the framework of centralized local computation. We introduce conflict coloring as a general symmetry-breaking task that includes all the aforementioned tasks as specific instantiations --- conflict coloring includes all locally checkable labeling tasks from [Naor\&Stockmeyer, STOC 1993]. Conflict coloring is characterized by two parameters $l$ and $d$, where the former measures the amount of freedom given to the nodes for selecting their colors, and the latter measures the number of constraints which colors of adjacent nodes are subject to.We show that, in the standard LOCAL model for distributed network computing, if $l/d \textgreater{} \Delta$, then conflict coloring can be solved in $\tilde O(\sqrt{\Delta})+\log^*n$ rounds in $n$-node graphs with maximum degree $\Delta$, where $\tilde O$ ignores the polylog factors in $\Delta$. The dependency in~$n$ is optimal, as a consequence of the $\Omega(\log^*n)$ lower bound by [Linial, SIAM J. Comp. 1992] for $(\Delta+1)$-coloring. An important special case of our result is a significant improvement over the best known algorithm for distributed $(\Delta+1)$-coloring due to [Barenboim, PODC 2015], which required $\tilde O(\Delta^{3/4})+\log^*n$ rounds. Improvements for other variants of coloring, including $(\Delta+1)$-list-coloring, $(2\Delta-1)$-edge-coloring, $T$-coloring, etc., also follow from our general result on conflict coloring. Likewise, in the framework of centralized local computation algorithms (LCAs), our general result yields an LCA which requires a smaller number of probes than the previously best known algorithm for vertex-coloring, and works for a wide range of coloring problems.

1 Introduction

The introduction frames sublinear deterministic symmetry breaking as the central challenge and presents conflict coloring as a framework for addressing it. It motivates the framework, describes its algorithmic approach and scope, and situates the results among related coloring and local-computation work.

1.3 Other Related Work

  • The related-work discussion places distributed coloring among local symmetry-breaking tasks and notes that LOCAL round complexity measures how far information can travel.A t-round algorithm exchanges information only with nodes at distance at most t.Source: §1.1 · p. 2

1.1 Context and Objective

  • The introduction asks which LCL tasks admit deterministic o(∆) + O(log*n)-round algorithms, contrasting recent progress for (∆+1)-coloring with partial evidence for MIS-type problems.Prior to this work, (∆+1)-list-coloring had a sublinear-in-∆ bound only when the color set was sufficiently small.Source: §1.1 · p. 3

1.2 Our Results

  • Conflict coloring assigns candidate-color lists to nodes and edge-specific forbidden color pairs, allowing every LCL task to be represented in this framework.The same color pair need not be conflicting on every edge.Source: §1.2 · p. 4
  • When l/d > ∆, the generic distributed algorithm solves conflict coloring in n-node graphs in eO(∆)+log∗n rounds, with eO disregarding polylogarithmic factors in ∆.It also solves (∆+1)-coloring and classical variants, including (∆+1)-list-coloring and (2∆−1)-edge-coloring, improving the best known results for each.Source: §1.2 · p. 4
  • The generic threshold is essentially bounded by l/d > ∆: some instances with l/d ≤ ∆ defeat arbitrary-order greedy completion, and no qualifying MIS or matching instantiation is known.The authors suggest this may help explain why sublinear deterministic algorithms are elusive for those tasks.Source: §1.2 · p. 4
  • The simplification mechanism repeatedly constructs easier problems in constant rounds, solves the final problem locally, then converts each solution back in constant rounds.Each step increases list sizes while also increasing conflicts, but the conflict growth is slower than list growth.Source: §1.2 · pp. 4–5

1.3 Other Related Work

  • Prior centralized local algorithms included a (∆+1)-coloring LCA using ∆^O(∆²) · log*n probes per query; the paper also develops an LCA for list-coloring.The centralized model answers graph queries while maintaining consistency with an implicit global solution.Source: §1.2 · p. 5, §1.3 · p. 6

2 Model, Problem Setting, and Preliminaries

The section sets out the LOCAL model and defines conflict coloring as a general task in which adjacent nodes avoid forbidden color pairs. It relates the framework to LCL tasks and previews the paper’s approach.

2.1 The LOCAL Model

  • In the LOCAL model, nodes have unique identities and inputs, exchange messages synchronously with neighbors, and are measured by the rounds needed for all nodes to terminate.A t-round algorithm lets each node collect information from within t hops.Source: §2.1 · pp. 6–7

2.2 Conflict Coloring

  • Conflict coloring gives each node a color list and forbids specified color pairs across each edge; its conflict degree d bounds the number of conflicts per color per neighbor.Any LCL task can be represented by lists of good local labelings and conflicts between inconsistent neighboring labelings.Source: §2.2 · pp. 7–8

2.3 Organization and Proof Outline

  • The ratio l/d captures the balance between list size and conflicts: l/d > ∆ is the regime the paper targets, including (∆+1)-list-coloring but not its natural MIS representation.The section previews simplification routines and arbdefective coloring as tools for solving such instances.Source: §2.2 · p. 8, §2.3 · p. 8

3 Instance Simplification

This section repeatedly simplifies conflict-coloring instances to increase the list-size-to-conflict-degree ratio, then solves a sufficiently simplified instance locally. The resulting routine handles instances above a threshold determined by oriented degree and runs in logarithmic-star rounds.

3 Instance Simplification

  • Each one-round simplification transforms an instance into one with a larger l/d ratio, and valid outputs can be mapped back; intermediate instances may be general conflict-coloring problems even when the original is list-coloring.Iterating this transformation leads to an instance solvable without further communication.Source: §3 · pp. 9–10
  • If all nodes know the feasible input set I, have a proper s-coloring, and l > d∆s|I|, they can solve the instance without communication by assigning colors greedily from shared knowledge.Each node’s color depends on its input and its label in the proper coloring.Source: §3 · pp. 9–10
  • The proof bounds feasible inputs after t simplification steps and chooses t so the greedy criterion holds, then solves the simplified instance and reverses the transformations.The resulting general theorem gives O(log*d + log*∆) + log*n rounds when an initial O(∆^2) coloring is computed in log*n + O(1) rounds.Source: §3 · pp. 11–12
  • A (10∆^2 ln ∆)-list-coloring can be found in log*n + O(log*∆) rounds, and the routine serves as a building block for instances with smaller l/d.The next section applies the routine to conflict coloring when l/d > ∆.Source: §3 · p. 12

4 Conflict Coloring with a Small Number of Colors

The algorithm handles conflict-coloring instances with lists of at least d·deg_G(v)+1 by coloring successive vertex subsets and recursively solving the remaining lower-degree graph. For constant or suitably bounded d, the stated round complexity is O(∆ log^2.5 ∆) + log*n.

4 Conflict Coloring with a Small Number of Colors

  • The procedure solves conflict-coloring instances with conflict degree at most d and lists of size at least d·deg_G(v)+1, including (∆+1)-list-coloring as a special case.The paper notes that for this special case d = 1 and Corollary 3.1 supplies a relevant ingredient.Source: §4 · pp. 12–13
  • The algorithm partitions vertices into k classes using arbdefective coloring and orients each class’s induced graph to have bounded outdegree, then colors the classes in stages.The arbdefective partition takes O(k log ∆) rounds.Source: §4 · pp. 12–13
  • At each stage, vertices receive colors compatible with previously colored neighbors; any still-uncolored vertex has at most 10β^2 ln ∆ uncolored neighbors.The algorithm recursively colors the residual graph with inherited lists that preserve the required list-size condition.Source: §4 · p. 13
  • For constant d or d with log*d = O(log ∆), the round complexity is O(∆ log^2.5 ∆) + log*n when lists satisfy |L(v)| ≥ d·deg_G(v) + 1.The (∆+1)-list-coloring case has d = 1.Source: §4 · pp. 12, 14

5 A Centralized Local Algorithm for Conflict-Coloring

The section adapts distributed conflict-coloring algorithms to centralized local computation, where a query is answered by probing part of the input graph. For sufficiently large l/d, it gives deterministic LCA probe bounds, including a list-coloring corollary.

Conflict-coloring LCA

  • The method adapts LOCAL algorithms to centralized local computation and improves the previously known probe complexity for (∆+1)-coloring.The section describes the resulting algorithm as a special case of its conflict-coloring LCA.Source: §5 · p. 14
  • For l/d ≥ 10∆² ln ∆, the deterministic oblivious LCA uses ∆O(log*∆) log*n probes per query.The theorem states this bound for conflict coloring; the section assumes log*d = O(log ∆).Source: §5 · p. 14
  • A two-phase simulation uses a ∆²-coloring LCA on the query node’s r-neighborhood, then simulates r rounds of conflict coloring without further probes.The first phase costs ∆^r poly(∆) log*n probes; choosing r = c log*∆ yields the stated bound for l/d ≥ 10∆² ln ∆.Source: §5 · p. 15

List-coloring

  • For list-coloring with lists of length at least 10∆² ln ∆, the corollary gives a deterministic oblivious LCA using ∆O(log*∆) log*n probes per query.The corollary also states a bound for lists of length at least ∆+1, but the supplied passage does not preserve that bound clearly.Source: §5 · p. 15

6 Conclusion

The conclusion frames conflict coloring both as a generalization of symmetry-breaking tasks and as a tool for describing intermediate instances in the algorithms. It also discusses the runtime scope and local-computation costs of the approach.

Conclusion

  • Deterministic round complexities for (∆+1)-coloring, (∆+1)-list-coloring, and conflict coloring with l/d > ∆ collapse to eO(∆) + log*n rounds.The conclusion contrasts this ratio condition with MIS, for which no deterministic o(∆) + log*n runtime approaches are known.Source: §6 · p. 15
  • Conflict coloring generalizes numerous symmetry-breaking tasks and serves as a tool for describing intermediate instances in the algorithms’ simplification technique.The paper presents these as two distinct roles for conflict coloring.Source: §6 · p. 15

Practical aspects

  • The most computationally intensive step enumerates a set I of size at most 2∆O(log*∆), polynomial in n when ∆ = (log n)o(1/log*n).The conclusion identifies this enumeration as the only bottleneck in local computation.Source: §6 · p. 15
  • A precomputed hash function can replace greedy color selection, reducing local computation time to ∆O(log*∆) while preserving the same asymptotic round complexity.The conclusion describes the approach as satisfactory for almost the entire range of ∆ sub-polynomial in n.Source: §6 · pp. 15–16

A Remark on Conflict Coloring Formulations for MIS

The proposition bounds the list-length to conflict-degree ratio for a conflict-coloring formulation of MIS that can be decoded locally without further communication. Its proof uses the two possible MIS outcomes on a star to force conflicts among colors.

Proposition

  • If a deterministic local decoding of conflict-coloring solutions on a star yields a valid MIS, then l/d ≤ 2.The condition is an if-and-only-if correspondence between valid conflict-coloring solutions and decoded MIS sets.Source: A Remark on Conflict Coloring… · p. 20

Proof

  • The proof uses the two possible MIS sets on a star to require both decoded color classes at the center and to force conflicts with corresponding leaf colors.These conflict requirements bound the conflict degree against the center’s two color classes, giving l ≤ 2d.Source: A Remark on Conflict Coloring… · p. 20

B Proof of Lemma 3.1

The proof constructs a simpler conflict-coloring instance by replacing colors with subsets of earlier colors and pruning subsets that create too many conflicts. It uses this construction to preserve feasible solutions while controlling the next instance’s lists and conflict degree.

Construction

  • Each next-instance color is a k_i-element subset of an earlier list, with subsets that generate too many neighborhood conflicts removed.The construction selects a constant proportion of the subsets, balancing list growth against growth in the number of conflicts.Source: B Proof of Lemma 3.1 · pp. 20–21

Solution conversion

  • The next conflict relation treats candidate colors as sets of earlier colors, and a valid next-instance solution can be converted to an earlier-instance solution in one communication round.A node selects an element from its output set that avoids conflicts with the corresponding sets of its out-neighbors.Source: B Proof of Lemma 3.1 · pp. 20–21

Parameter bounds

  • The construction is designed to satisfy the next instance’s conflict-degree bound while retaining nonempty lists.The proof bounds the number of subsets removed per neighbor and uses that bound to establish a lower bound on the resulting list size.Source: B Proof of Lemma 3.1 · pp. 21–22
Loading 1511.01287v2…