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.STACS.2014.75
URN: urn:nbn:de:0030-drops-44484
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4448/
Go to the corresponding LIPIcs Volume Portal

Araujo, Julio ; Nisse, Nicolas ; Pérennes, Stéphane

Weighted Coloring in Trees

pdf-format:
6.pdf (0.7 MB)

Abstract

A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a color. For a vertex-weighted graph, the weight of a color is the maximum weight of its vertices. The weight of a coloring is the sum of the weights of its colors. Guan and Zhu (1997) defined the weighted chromatic number of a vertex-weighted graph G as the smallest weight of a proper coloring of G. If vertices of a graph have weight 1, its weighted chromatic number coincides with its chromatic number. Thus, the problem of computing the weighted chromatic number, a.k.a. Max Coloring Problem, is NP-hard in general graphs. It remains NP-hard in some graph classes as bipartite graphs. Approximation algorithms have been designed in several graph classes, in particular, there exists a PTAS for trees. Surprisingly, the time-complexity of computing this parameter in trees is still open.

The Exponential Time Hypothesis (ETH) states that 3-SAT cannot be solved in sub-exponential time. We show that, assuming ETH, the best algorithm to compute the weighted chromatic number of n-node trees has time-complexity n O(log(n)). Our result mainly relies on proving that, when computing an optimal proper weighted coloring of a graph G, it is hard to combine colorings of its connected components.

BibTeX - Entry

@InProceedings{araujo_et_al:LIPIcs:2014:4448,
  author =	{Julio Araujo and Nicolas Nisse and St{\'e}phane P{\'e}rennes},
  title =	{{Weighted Coloring in Trees}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{75--86},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4448},
  URN =		{urn:nbn:de:0030-drops-44484},
  doi =		{10.4230/LIPIcs.STACS.2014.75},
  annote =	{Keywords: Weighted Coloring, Max Coloring, Exponential Time Hypothesis, 3-SAT}
}

Keywords: Weighted Coloring, Max Coloring, Exponential Time Hypothesis, 3-SAT
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

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