Dual Parameterization of Weighted Coloring - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Algorithmica Year : 2020

Dual Parameterization of Weighted Coloring

Abstract

Given a graph G, a proper k-coloring of G is a partition c = (S i) i∈[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∈Si w(v) and the weight of a coloring c as w(c) = k i=1 w(i). Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair (G, w), denoted by σ(G, w), as the minimum weight of a proper coloring of G. The problem of determining σ(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 σ(G, w) ≤ v∈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 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 ⊆ coNP/poly, even on split graphs with only two different weights. Finally, we identify classes of graphs allowing for polynomial kernels, namely interval graphs, comparability graphs, and subclasses of circular-arc and split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.
Fichier principal
Vignette du fichier
ALGO-D-18-00267R2.pdf (1000.74 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-02989870 , version 1 (05-11-2020)

Licence

Attribution

Identifiers

Cite

Júlio Araújo, Victor A Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, et al.. Dual Parameterization of Weighted Coloring. Algorithmica, 2020, 82 (8), pp.2316-2336. ⟨10.1007/s00453-020-00686-7⟩. ⟨lirmm-02989870⟩
17 View
57 Download

Altmetric

Share

Gmail Facebook X LinkedIn More