Araújo, Júlio ;
Campos, Victor A. ;
Lima, Carlos Vinícius G. C. ;
Fernandes dos Santos, Vinícius ;
Sau, Ignasi ;
Silva, Ana
Dual Parameterization of Weighted Coloring
Abstract
Given a graph G, a proper kcoloring 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 NPhard on split graphs, unsolvable on nvertex trees in time n^{o(log n)} unless the ETH fails, and W[1]hard on forests parameterized by the size of a largest tree.
We focus on the socalled dual parameterization of the problem: given a vertexweighted 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^{k1}+1) (k1) 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:112:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770842},
ISSN = {18688969},
year = {2019},
volume = {115},
editor = {Christophe Paul and Michal Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10213},
URN = {urn:nbn:de:0030drops102134},
doi = {10.4230/LIPIcs.IPEC.2018.12},
annote = {Keywords: weighted coloring, max coloring, parameterized complexity, dual parameterization, FPT algorithms, polynomial kernels, split graphs, interval graphs}
}
05.02.2019
Keywords: 

weighted coloring, max coloring, parameterized complexity, dual parameterization, FPT algorithms, polynomial kernels, split graphs, interval graphs 
Seminar: 

13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Issue date: 

2019 
Date of publication: 

05.02.2019 