Aboulker, Pierre ;
Bonnet, Édouard ;
Kim, Eun Jung ;
Sikora, Florian
Grundy Coloring & Friends, HalfGraphs, Bicliques
Abstract
The firstfit coloring is a heuristic that assigns to each vertex, arriving in a specified order σ, the smallest available color. The problem Grundy Coloring asks how many colors are needed for the most adversarial vertex ordering σ, i.e., the maximum number of colors that the firstfit coloring requires over all possible vertex orderings. Since its inception by Grundy in 1939, Grundy Coloring has been examined for its structural and algorithmic aspects. A bruteforce f(k)n^{2^{k1}}time algorithm for Grundy Coloring on general graphs is not difficult to obtain, where k is the number of colors required by the most adversarial vertex ordering. It was asked several times whether the dependency on k in the exponent of n can be avoided or reduced, and its answer seemed elusive until now. We prove that Grundy Coloring is W[1]hard and the bruteforce algorithm is essentially optimal under the Exponential Time Hypothesis, thus settling this question by the negative.
The key ingredient in our W[1]hardness proof is to use socalled halfgraphs as a building block to transmit a color from one vertex to another. Leveraging the halfgraphs, we also prove that bChromatic Core is W[1]hard, whose parameterized complexity was posed as an open question by Panolan et al. [JCSS '17]. A natural followup question is, how the parameterized complexity changes in the absence of (large) halfgraphs. We establish fixedparameter tractability on K_{t,t}free graphs for bChromatic Core and Partial Grundy Coloring, making a step toward answering this question. The key combinatorial lemma underlying the tractability result might be of independent interest.
BibTeX  Entry
@InProceedings{aboulker_et_al:LIPIcs:2020:11919,
author = {Pierre Aboulker and {\'E}douard Bonnet and Eun Jung Kim and Florian Sikora},
title = {{Grundy Coloring & Friends, HalfGraphs, Bicliques}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {58:158:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771405},
ISSN = {18688969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11919},
URN = {urn:nbn:de:0030drops119190},
doi = {10.4230/LIPIcs.STACS.2020.58},
annote = {Keywords: Grundy coloring, parameterized complexity, ETH lower bounds, K_{t,t}free graphs, halfgraphs}
}
04.03.2020
Keywords: 

Grundy coloring, parameterized complexity, ETH lower bounds, K_{t,t}free graphs, halfgraphs 
Seminar: 

37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Issue date: 

2020 
Date of publication: 

04.03.2020 