Weighted Coloring in Trees

Julio Araujo 1 Nicolas Nisse 2 Stéphane Pérennes 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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 defined the weighted chromatic number of a vertex-weighted graph G as the smallest weight of a proper coloring of G (1997). 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-exponen-tial time. We show that, assuming ETH, the best algorithm to compute the weighted chromatic number of n-node trees has time-complexity n Θ(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.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2014, 28 (4), pp.2029 - 2041. <10.1137/140954167>
Liste complète des métadonnées


https://hal.inria.fr/hal-01109194
Contributeur : Nicolas Nisse <>
Soumis le : dimanche 25 janvier 2015 - 14:38:27
Dernière modification le : mercredi 7 octobre 2015 - 01:14:17
Document(s) archivé(s) le : vendredi 11 septembre 2015 - 09:15:22

Fichier

journal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Julio Araujo, Nicolas Nisse, Stéphane Pérennes. Weighted Coloring in Trees. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2014, 28 (4), pp.2029 - 2041. <10.1137/140954167>. <hal-01109194>

Partager

Métriques

Consultations de
la notice

199

Téléchargements du document

100