2026-08-11T08:10:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10213 2024-03-06T10:44:16Z ddc:004 open_access

Dual Parameterization of Weighted Coloring Araújo, Júlio Campos, Victor A. Lima, Carlos Vinícius G. C. Fernandes dos Santos, Vinícius Sau, Ignasi Silva, Ana weighted coloring max coloring parameterized complexity dual parameterization FPT algorithms polynomial kernels split graphs interval graphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Júlio Araújo and Victor A. Campos and Carlos Vinícius G. C. Lima and Vinícius Fernandes dos Santos and Ignasi Sau and Ana Silva 2019 Is Part Of LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2018.12 urn:nbn:de:0030-drops-102134 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.12 eng https://creativecommons.org/licenses/by/3.0/legalcode