The Library
Online edge coloring algorithms via the nibble method
Tools
Bhattacharya, Sayan, Grandoni, Fabrizio and Wajc, David (2021) Online edge coloring algorithms via the nibble method. In: ACM-SIAM Symposium on Discrete Algorithms (SODA21), Virtual, 10-13 Jan 2021. Published in: SODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms pp. 2830-2841. ISBN 9781611976465. doi:10.1137/1.9781611976465.168
|
PDF
WRAP-online-edge-coloring-algorithms-nibble-method-Bhattacharya-2020.pdf - Accepted Version - Requires a PDF viewer. Download (950Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611976465.168
Abstract
Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL'92] conjectured that an online (1 + o(1))Δ-edge-coloring algorithm exists for n-node graphs of maximum degree Δ = ω(log n). This conjecture remains open in general, though it was recently proven for bipartite graphs under one-sided vertex arrivals by Cohen et al. [FOCS'19]. In a similar vein, we study edge coloring under widely-studied relaxations of the online model.
Our main result is in the random-order online model. For this model, known results fall short of the Bar-Noy et al. conjecture, either in the degree bound [Aggarwal et al. FOCS'03], or number of colors used [Bahmani et al. SODA'10]. We achieve the best of both worlds, thus resolving the Bar-Noy et al. conjecture in the affirmative for this model.
Our second result is in the adversarial online (and dynamic) model with recourse. A recent algorithm of Duan et al. [SODA'19] yields a (1 + ϵ) Δ-edge-coloring with poly(logn/ϵ) recourse. We achieve the same with poly(1/ϵ) recourse, thus removing all dependence on n.
Underlying our results is one common offline algorithm, which we show how to implement in these two online models. Our algorithm, based on the Rödl Nibble Method, is an adaptation of the distributed algorithm of Dubhashi et al. [TCS'98]. The Nibble Method has proven successful for distributed edge coloring. We display its usefulness in the context of online algorithms.
Item Type: | Conference Item (Paper) | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | |||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Graph coloring, Algorithms, Graph theory | |||||||||||||||
Journal or Publication Title: | SODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms | |||||||||||||||
Publisher: | Society for Industrial and Applied Mathematics : ACM | |||||||||||||||
ISBN: | 9781611976465 | |||||||||||||||
Official Date: | January 2021 | |||||||||||||||
Dates: |
|
|||||||||||||||
Page Range: | pp. 2830-2841 | |||||||||||||||
DOI: | 10.1137/1.9781611976465.168 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Reuse Statement (publisher, data, author rights): | “First Published in SODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms 2021, published by the Society for Industrial and Applied Mathematics (SIAM)” and the copyright notice as stated in the article itself (e.g., “Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.”) | |||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
Date of first compliant deposit: | 28 November 2019 | |||||||||||||||
Date of first compliant Open Access: | 2 December 2019 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Conference Paper Type: | Paper | |||||||||||||||
Title of Event: | ACM-SIAM Symposium on Discrete Algorithms (SODA21) | |||||||||||||||
Type of Event: | Conference | |||||||||||||||
Location of Event: | Virtual | |||||||||||||||
Date(s) of Event: | 10-13 Jan 2021 | |||||||||||||||
Related URLs: | ||||||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year