 License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-102134
URL:

; ; ; ; ;

### Dual Parameterization of Weighted Coloring

 pdf-format:

### Abstract

Given a graph G, a proper k-coloring of G is a partition c = (S_i)_{i in [1,k]} of V(G) into k stable sets S_1,..., S_k. Given a weight function w: V(G) -> R^+, the weight of a color S_i is defined as w(i) = max_{v in S_i} w(v) and the weight of a coloring c as w(c) = sum_{i=1}^{k} w(i). Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair (G,w), denoted by sigma(G,w), as the minimum weight of a proper coloring of G. The problem of determining sigma(G,w) has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on n-vertex trees in time n^{o(log n)} unless the ETH fails, and W-hard on forests parameterized by the size of a largest tree.
We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph (G,w) and an integer k, is sigma(G,w) <= sum_{v in V(G)} w(v) - k? This parameterization has been recently considered by Escoffier [WG, 2016], who provided an FPT algorithm running in time 2^{O(k log k)} * n^{O(1)}, and asked which kernel size can be achieved for the problem.
We provide an FPT algorithm running in time 9^k * n^{O(1)}, and prove that no algorithm in time 2^{o(k)} * n^{O(1)} exists under the ETH. On the other hand, we present a kernel with at most (2^{k-1}+1) (k-1) vertices, and rule out the existence of polynomial kernels unless NP subseteq coNP/poly, even on split graphs with only two different weights. Finally, we identify some classes of graphs on which the problem admits a polynomial kernel, in particular interval graphs and subclasses of split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.

### BibTeX - Entry

```@InProceedings{arajo_et_al:LIPIcs:2019:10213,
author =	{J{\'u}lio Ara{\'u}jo and Victor A. Campos and Carlos Vin{\'i}cius G. C. Lima and Vin{\'i}cius Fernandes dos Santos and Ignasi Sau and Ana Silva},
title =	{{Dual Parameterization of Weighted Coloring}},
booktitle =	{13th International Symposium on Parameterized and Exact  Computation (IPEC 2018)},
pages =	{12:1--12:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-084-2},
ISSN =	{1868-8969},
year =	{2019},
volume =	{115},
editor =	{Christophe Paul and Michal Pilipczuk},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 