License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2018.12
URN: urn:nbn:de:0030-drops-102134
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10213/
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 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[1]-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},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10213},
URN = {urn:nbn:de:0030-drops-102134},
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}
}
|
Keywords: |
|
weighted coloring, max coloring, parameterized complexity, dual parameterization, FPT algorithms, polynomial kernels, split graphs, interval graphs |
|
Collection: |
|
13th International Symposium on Parameterized and Exact Computation (IPEC 2018) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
05.02.2019 |
