Dual parameterization of weighted coloring

DOI10.1007/S00453-020-00686-7zbMATH Open1452.68129arXiv1805.06699OpenAlexW3081356430MaRDI QIDQ786042

Author name not available (Why is that?)

Publication date: 12 August 2020

Published in: (Search for Journal in Brave)

Abstract: Given a graph $G$, a proper $k$-coloring of $G$ is a partition $c=(S_i{)}_{iin[1,k]}$ of $V(G)$ into $k$ stable sets $S_1,ldots,S_k$. Given a weight function $w:V(G)omathbb{R}^{+}$, the weight of a color $S_i$ is defined as $w(i)=ma{x}_{vin{S}_i}w(v)$ and the weight of a coloring $c$ as $w(c)=su{m}_{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(logn)}$ unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. In this article we provide some positive results for the problem, by considering its so-called dual parameterization: given a vertex-weighted graph $(G,w)$ and an integer $k$, the question is whether $sigma(G,w)leqsu{m}_{vinV(G)}w(v)-k$. We prove that this problem is FPT by providing an algorithm running in time $9^{k}cdot{n}^{O(1)}$, and it is easy to see that no algorithm in time $2^{o(k)}cdot{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 we rule out the existence of polynomial kernels unless $sfNPsubseteqsfcoNP/sfpoly$, 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.

Full work available at URL: https://arxiv.org/abs/1805.06699

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Dual parameterization of weighted coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q786042)