Group for Research in Decision Analysis

# Lower Bounds and a Tabu Search Algorithm for the Minimum Deficiency Problem

## Mathieu Bouchard, Alain Hertz, and Guy Desaulniers

An edge coloring of a graph $G = (V,E)$ is a function $c:E \rightarrow N$ that assigns a color $c(e)$ to each edge $e\in E$ such that $c(e) \neq c(e')$ whenever $e$ and $e'$ have a common endpoint. Denoting the set of colors assigned to the edges incident to a vertex $v\in V$, and $D_v(G, c)$ the minimum number of integers which must be added to $S_v(G, c)$ to form an interval, the deficiency $D(G, c)$ of an edge coloring $c$ is defined as the sum $\sum_{v\in V} D_v(G, c)$, and the span of $c$ is the number of colors used in $c$. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them having a known optimal deficiency.

, 27 pages