Exact algorithms for a discrete metric labeling problem (Q5920404)

Let \(G=(V,E)\) be an edge-weighted undirected graph, and \(C\) be a finite set of colors. Furthermore for each vertex \(v\) a non-empty subset \(C_v\) of colors is associated. A vertex coloring \(\varphi\) is feasible if for each \(v\) we have \(\varphi(v) \in C_v.\) To find a feasible coloration which minimizes the total edge weights of the color-changing edges (edges with differently colored vertices) is called discrete metric labeling problem, and was introduced by this paper. This is a special case of the metric labeling problem of J. Kleinberg and E. Tardos (therefore the approximation algorithm of the latter also works on it). The problem is also closely related to the colored multiway cut problem of P. L. Erdős and L. A. Székely. Finally the problem provides a mean to deal with flexible manufacturing systems. The main contributions of the paper is the exact solutions of discrete metric labeling problem for trees, cycles and graphs with small tree-width. It also introduces a general branch and bound algorithm to solve the general (NP-hard) problem.