Exact algorithms for a discrete metric labeling problem

In this work we deal with a vertex coloring problem where we are given an undirected graph G = ( V , E ) and a set of colors C = { 1 , 2 , … k } . With each edge e ∈ E is associated a weight and with each vertex v ∈ V a subset ∅ ≠ C v ⊆ C . A coloring of the vertices is feasible if each vertex v is colored with a color of C v . A coloring uniquely defines a subset E ′ ⊆ E of edges having different colored endpoints. The problem of finding a feasible coloring which defines a minimum weight E ′ is, in general, NP-complete. In this work an implicit enumeration scheme for finding such an optimal coloring is presented. Upper and lower bounds evaluations are based on a O ( | V | k ) combinatorial algorithm for the special case of trees and cacti.