The Library
Nibbling at long cycles : dynamic (and static) edge coloring in optimal time
Tools
Bhattacharya, Sayan, Costa, Martin, Panski, Nadav and Solomon, Shay (2024) Nibbling at long cycles : dynamic (and static) edge coloring in optimal time. In: 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Virginia, USA, 7-10 Jan 2024. Published in: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 3393-3440. ISBN 9781611977912. doi:10.1137/1.9781611977912.122
|
PDF
Nibbling-long-cycles-dynamic-static-edge-coloring-optimal-time-23.pdf - Accepted Version - Requires a PDF viewer. Download (1058Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611977912.122
Abstract
We consider the problem of maintaining a (1 + ɛ)∆-edge coloring in a dynamic graph G with n nodes and maximum degree at most Δ. The state-of-the-art update time is Oɛ(polylog(n)), by Duan, He and Zhang [SODA’19] and by Christiansen [STOC’23], and more precisely O(log7 n/ɛ2), where Δ = Ω(log2 n/ɛ2).
The following natural question arises: What is the best possible update time of an algorithm for this task? More specifically, can we bring it all the way down to some constant (for constant ɛ)? This question coincides with the static time barrier for the problem: Even for (2Δ — 1)-coloring, there is only a naive O(m log Δ)-time algorithm.
We answer this fundamental question in the affirmative, by presenting a dynamic (1 + ɛ)Δ-edge coloring algorithm with O(log4(1/ɛ)/ɛ9) update time, provided Δ = Ωɛ (polylog(n)). As a corollary, we also get the first linear time (for constant ɛ) static algorithm for (1 + ɛ)Δ-edge coloring; in particular, we achieve a running time of O(m log(1/ɛ)/ɛ2).
We obtain our results by carefully combining a variant of the Nibble algorithm from Bhattacharya, Grandoni and Wajc [SODA’21] with the subsampling technique of Kulkarni, Liu, Sah, Sawhney and Tarnawski [STOC’22].
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Journal or Publication Title: | Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | ||||||
Publisher: | SIAM | ||||||
ISBN: | 9781611977912 | ||||||
Book Title: | Moment intermittency in the PAM with asymptotically singular noise | ||||||
Official Date: | 4 January 2024 | ||||||
Dates: |
|
||||||
Page Range: | pp. 3393-3440 | ||||||
DOI: | 10.1137/1.9781611977912.122 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Re-use Statement: | First Published in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) in 2024, published by the Society for Industrial and Applied Mathematics (SIAM)” © 2024 by the Society for Industrial and Applied Mathematics. Unauthorized reproduction of this article is prohibited.”) | ||||||
Access rights to Published version: | Free Access (unspecified licence, 'bronze OA') | ||||||
Copyright Holders: | © 2024 by the Society for Industrial and Applied Mathematics | ||||||
Date of first compliant deposit: | 21 November 2023 | ||||||
Date of first compliant Open Access: | 22 April 2024 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024) | ||||||
Type of Event: | Other | ||||||
Location of Event: | Virginia, USA | ||||||
Date(s) of Event: | 7-10 Jan 2024 | ||||||
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