Sayan Bhattacharya is an Associate Professor at the Dept. of Computer Science, University of Warwick, UK. He was a postdoc at MPI-INF in the D1 group from January, 2013 - June, 2014.

Please find his homepage here: https://www.dcs.warwick.ac.uk/~u1671158/

AG 1   Info

AG Audience

English

45 Minutes

Saarbrücken

For any arbitrary small constant \epsilon > 0, we consider the problem of maintaining a (1+\epsilon)\Delta-edge coloring in a dynamic graph G with n nodes and maximum degree at most \Delta. The state-of-the-art update time for this problem was polylogarithmic in n, due to Duan, He and Zhang [SODA'19] and Christiansen [STOC'23].

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? This question coincides with the static time barrier for the problem: Even for (2\Delta-1)-coloring, there was only a naïve O(m \log \Delta)-time algorithm.

We answer this fundamental question in the affirmative, provided \Delta is sufficiently large. As a corollary, we also get the first linear time static algorithm for (1+\epsilon)\Delta-edge coloring.

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].

This talk is based on joint work with Martin Costa, Nadav Panski and Shay Solomon, which appeared in SODA'24.

Nidhi Rathi

+49 681 9325 1134

--email hidden

Zoom

897 027 2575

passcode not visible

logged in users only