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/
Go to the corresponding LIPIcs Volume Portal


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

pdf-format:
LIPIcs-IPEC-2018-12.pdf (0.5 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI