Data: 17/09/2020, às 14:00 horas (GMT-3, horário de Brasília).
Título: Dual Parameterization of Weighted Coloring
Palestrante: Júlio Araújo (UFC)


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,\ldots, 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) \eq \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^{\Ocal(k \log k)} \cdot n^{\Ocal(1)}$, and asked which kernel size can be achieved for the problem.

We provide an FPT algorithm in time $9^k \cdot n^{\Ocal(1)}$, and prove that no algorithm in time $2^{o(k)} \cdot n^{\Ocal(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. This is an improvement on the algorithm of Escoffier and an answer for his question about the best running time. 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.

Joint work with Victor A. Campos, Carlos Vinícius G. C. Lima, Vinicius Fernandes dos Santos, Ignasi Sau & Ana Silva.