Weighted Coloring in Trees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2013

Weighted Coloring in Trees

Résumé

A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a {\it color}. For a vertex-weighted graph, the {\it weight of a color} is the maximum weight of its vertices. The {\it weight of a coloring} is the sum of the weights of its colors. Guan and Zhu defined the {\it 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. Therefore, the problem of computing the weighted chromatic number is NP-complete in general graphs. This problem remains NP-complete in some particular graph classes as bipartite graphs. In their seminal paper, Guan and Zhu asked whether the weighted chromatic number of bounded tree-width graphs (partial $k$-trees) can be computed in polynomial-time. Escoffier et al. designed a polynomial-time approximation scheme for computing the weighted chromatic number of partial $k$-trees (2006), and Kavitha and Mestre provided polynomial-time exact algorithms for sub-classes of trees (2009). 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^{\Theta(\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, even when $G$ is a forest.
Nous prouvons que, en supposant qu'il n'existe aucun algorithme sous-exponentiel pour résoudre 3-SAT (ETH), alors le meilleur algorithme pour résoudre le probléme de coloration pondérée dans les arbres a une complexité de $n^{\Theta(\log n)}$, oú $n$ est la taille de l'entrée.
Fichier principal
Vignette du fichier
RR-8249.pdf (913.8 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00794622 , version 1 (26-02-2013)
hal-00794622 , version 2 (07-03-2013)

Identifiants

  • HAL Id : hal-00794622 , version 2

Citer

Julio Araujo, Nicolas Nisse, Stéphane Pérennes. Weighted Coloring in Trees. [Research Report] RR-8249, INRIA. 2013. ⟨hal-00794622v2⟩
560 Consultations
398 Téléchargements

Partager

Gmail Facebook X LinkedIn More