Parameterized Complexity of Grundy Coloring and its variants

Speaker(s)

Edouard Bonnet

Affiliation

ENS Lyon

Date

Oct. 10, 2019, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

(Connected/Partial/Weak) Grundy Coloring, b-Coloring, b-Chromatic Core, etc. are maximization coloring problems, where one asks for the worst case of a first-fit coloring strategy. They were introduced to analyze if some coloring heuristics have performance guarantee. We investigate the parameterized complexity of these problems with respect to the number of colors k. This offers quite a diversity since we show that -Weak Grundy is FPT -Grundy is W[1]-complete (as well as b-Chromatic Core) -Connected Grundy is paraNP-complete and Partial Grundy is still open! For Grundy Coloring an easy argument gives a double-exponential XP algorithm in n^{2^k} that we prove essentially optimal under the Exponential-Time Hypothesis. The key ingredient here is the use of so-called half-graphs (think 2K_2-free bipartite graphs). It seems that half-graphs, and the more restricted bicliques, are essential in making Grundy and b-Chromatic Core W[1]-hard. As a first step, we show that b-Chromatic Core and Partial Grundy can be solved in FPT time in K_{t,t}-free graphs. This uses Random Separation for the bounded-degree case, and a handful of Ramsey-type arguments when the degree is large. The talk follows joint works with Pierre Aboulker, Florent Foucaud, Eun Jung Kim, and Florian Sikora.

---