Weighted Coloring in Trees

Description

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.

Abstract (French)

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.

Additional details