Show simple item record

Grundy Coloring & Friends, Half-Graphs, Bicliques

dc.contributor.authorAboulker, Pierre
dc.contributor.authorBonnet, Edouard
HAL ID: 171728
ORCID: 0000-0002-1653-5822
dc.contributor.authorKim, Eun Jung
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258
dc.date.accessioned2020-09-29T15:59:02Z
dc.date.available2020-09-29T15:59:02Z
dc.date.issued2020
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/21014
dc.language.isoenen
dc.subject.ddc511en
dc.titleGrundy Coloring & Friends, Half-Graphs, Bicliques
dc.typeCommunication / Conférence
dc.description.abstractenThe first-fit 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 first-fit 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 brute-force f(k)n^{2^{k-1}}-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 brute-force 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 so-called half-graphs as a building block to transmit a color from one vertex to another. Leveraging the half-graphs, we also prove that b-Chromatic Core is W[1]-hard, whose parameterized complexity was posed as an open question by Panolan et al. [JCSS '17]. A natural follow-up question is, how the parameterized complexity changes in the absence of (large) half-graphs. We establish fixed-parameter tractability on K_{t,t}-free graphs for b-Chromatic 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.
dc.identifier.citationpages58:1-58:18
dc.relation.ispartoftitle37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
dc.relation.ispartofpublnameSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
dc.identifier.urlsitehttps://dx.doi.org/10.4230/LIPIcs.STACS.2020.58
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.ispartofisbn978-3-95977-140-5
dc.relation.conftitle37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
dc.relation.confdate2020-03
dc.relation.confcountryFRANCE
dc.relation.forthcomingnonen
dc.identifier.doi10.4230/LIPIcs.STACS.2020.58
dc.description.ssrncandidatenon
dc.description.halcandidatenon
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2020-12-17T09:13:40Z


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record