Sparsity-Parameterised Dynamic Edge Colouring

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

2 Downloads (Pure)

Abstract

We study the edge-colouring problem, and give efficient algorithms where the number of colours is parameterised by the graph’s arboricity, α. In a dynamic graph, subject to insertions and deletions, we give a deterministic algorithm that updates a proper Δ + O(α) edge colouring in poly(log n) amortized time. Our algorithm is fully adaptive to the current value of the maximum degree and arboricity. In this fully-dynamic setting, the state-of-the-art edge-colouring algorithms are either a randomised algorithm using (1 + ε)Δ colours in poly(log n, ε^{-1}) time per update, or the naive greedy algorithm which is a deterministic 2Δ -1 edge colouring with log(Δ) update time. Compared to the (1+ε)Δ algorithm, our algorithm is deterministic and asymptotically faster, and when α is sufficiently small compared to Δ, it even uses fewer colours. In particular, ours is the first Δ+O(1) edge-colouring algorithm for dynamic forests, and dynamic planar graphs, with polylogarithmic update time. Additionally, in the static setting, we show that we can find a proper edge colouring with Δ + 2α colours in O(mlog n) time. Moreover, the colouring returned by our algorithm has the following local property: every edge uv is coloured with a colour in {1, max{deg(u), deg(v)} + 2α}. The time bound matches that of the greedy algorithm that computes a 2Δ-1 colouring of the graph’s edges, and improves the number of colours when α is sufficiently small compared to Δ.
Original languageEnglish
Title of host publicationProceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)
Volume294
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date2024
Pages20:1-20:18
ISBN (Print)978-3-95977-318-8
DOIs
Publication statusPublished - 2024

Keywords

  • Edge colouring
  • Arboricity
  • Hierarchical partition
  • Dynamic algorithms
  • Amortized analysis

Fingerprint

Dive into the research topics of 'Sparsity-Parameterised Dynamic Edge Colouring'. Together they form a unique fingerprint.

Cite this