**Backtrack free solutions in Networks of Binary Constraints ** **and Graph Coloring**
**Massimiliano Caramia**
*Dipartimento di Informatica, Sistemi e Produzione*
*University of Rome “Tor Vergata”', Via di Tor Vergata, 110 - 00133 Rome, Italy*
*Tel.: +39-06-72597339 - E-mail: caramia@disp.uniroma2.it*
## **Paolo Dell'Olmo**
*Dipartimento di Statistica, Probabilit‡ e Statistiche Applicate*
*University of Rome “La Sapienza”, Piazzale Aldo Moro, 5 - 00185 Rome, Italy*
*Tel.: +39-06-49910771 - E-mail: dellolmo@iasi.rm.cnr.it*
## **Extended abstract**
The aim of the coloring problem is to assign to each node of an undirected graph, a label (color) such that no two adjacent nodes receive the same color and the number of used labels is minimum. In the field of combinatorial optimization this is one of the hardest to solve problem and its NP-completeness has been proved in general and in a number of particular cases [5]. A large body of efforts in Artificial Intelligence has been concentrated in Constraint Satisfaction Problems (CSP) [2] which are motivated by several applications as pattern recognition and image processing. In this paper we represent the coloring problem as a CSP and show how some results obtained for Networks of Binary Constraints can be used to define new graph classes colorable in polynomial time. Most of the graphs which are known to be efficiently colorable belong to the class of perfect graphs and the corresponding algorithms rely either on the topological structure of the graph [6] or on the integrality of the solution of the linear programming formulation [7]. The characterization given in this paper is derived from the CSP formulation of the problem and is capable of including graphs which are not perfect.
A Constraint Satisfaction Problem (CSP) [2] involves a set of *n* variables *X*_{1}, *X*_{2}, ….., *X*_{n} and a set of *n* domains, *D*_{1}, *D*_{2}, …., *D*_{n} where each *D*_{i} defines the set of values that the variable *X*_{i} may assume. A solution of the CSP is an assignment of values to all the variables which satisfy a given set of constraints. A Binary CSP is one in which all the constraints involve only pairs of variables. A binary constraint between variables *X*_{i}, *X*_{j} is a subset of the Cartesian product *D*_{i} *D*_{j}. A Binary CSP can be associated with a constraint graph in which nodes represent variables and arcs connect pairs of constrained variables. A constraint graph admits *backtrack-free* solutions if, given a total order to the variables, it is possible to assign values to variables one by one, without changing previous assignments.
**Definition 1**. [9] An arc *X*_{i}, *X*_{j} is arc-consistent iff for any value *xD*_{i}, there is a value *yD*_{j} that satisfies the binary constraint between *X*_{i} and *X*_{j}.
**Definition 2**. [9] A constraint graph is arc-consistent if each of its arcs is arc-consistent.
**Theorem 1**. [4] If a constraint graph is a tree and if it is arc-consistent, then it admits backtrack-free solutions.
The graph coloring problem can be stated as a Binary CSP where *X*_{1}, *X*_{2}, ….., *X*_{n} are the variables which represent respectively the colors to be assigned to the *n* nodes in *V*, and in the constraint graph there is an arc between *X*_{i}, *X*_{j}, whenever the corresponding vertices *i*, *jV* are adjacent in *G*. The binary constraints are of the form {(*x*, *y*), *xD*_{i}, *yD*_{j} : *xy* }. For the sake of simplicity we will call the node *X*_{i} as *i*. Defined the domains *D*_{i} for each vertex *iV*, and substituted *arcs* with *edges*, due to the symmetry of coloring constraints, and domain *D*_{i} with list *L*_{i}, definitions 1 and 2 can be restated in terms of coloring of the graph *G*=(*V*,*E*).
**Definition 3**. An edge (*i*, *j*)*E * is edge-consistent iff for any color *xL*_{i}, there is a color *yL*_{j} such that *xy*.
**Definition 4**. A graph *G*=(*V*,*E*) is edge-consistent if every (*i*, *j*)*E* is edge-consistent.
The major problem for taking an advantage from the above definitions is related to the setting of lists. This is probably the reason for which in [2] the authors do not see how the two problems could be effectively related. Clearly, lists with large cardinality (say quite greater than the chromatic number) would allow to find more easily a backtrack free solution, but in this case one would get a very poor coloring solution. Our idea, which in some cases brings to a polynomial coloring, is based on assigning domains which are obtained from a lower bound on the chromatic number of a graph. The lower bound we use is the maximum clique of *G*.
Let *W* be a maximum clique of *G*, with |*W*|=, and let *N*(*W*) be the neighborhood of *W*. Moreover, let *G*_{NW} denote the subgraph induced by *WN*(*W*) and let *G*_{N} be the subgraph induced by *N*(*W*). Assign to the vertices in *W* colors from 1 to , and assign lists of colors (candidate colors) to the nodes in *N*(*W*) as follows: first set *L*_{i}={1, …., } for each node *iN*(*W*); then for each *L*_{i} delete the colors which have been already assigned to the nodes in *W* adjacent to *i*. Call this assignment *A*. Hence if we are able to solve the CSP with lists equal to then we find an optimal solution to the problem.
**Proposition 1**. In *G*_{NW}, referring to the assignment *A*, the following properties hold:
*P*_{1}: |* L*_{i} | 1 for each node *iN*(*W*);
*P*_{2}: if *L*_{i}=*L*_{j} for adjacent nodes *i*, *jN*(*W*), then |*L*_{i}*L*_{j}| 2.
**Proof**: We prove the properties by contradiction. Assume |*L*_{i}| = 0 for some node *iN*(*W*). Thus *i* has to be connected with all the nodes in *W* making *W* not maximum. Hence |*L*_{i} | 1. Assume now that *i* and *j* are adjacent in *G*_{N} and *L*_{i}=*L*_{j} with |*L*_{i}*L*_{j}| =1. Then both *i* and *j* must be adjacent to the same subset of -1 nodes of *W* with which they would form a clique of size +1.
Exploiting property *P*_{1} of the previous proposition, in the follow we examine separately two different cases: the former in which all nodes in *N*(*W*) have a list with cardinality greater than one, and the latter in which some list remains with only one color. The objective is to define a backtrack free assignment that tries to extend the precoloring [8] of the maximum clique. If all the nodes *jN*(*W*) have lists |*L*_{i} | 2, the subgraph *G*_{N} is edge-consistent and a first result can be read out directly from theorem 1:
**Theorem 2**. If *G*_{N }is a forest, then *G*_{NW} has chromatic number .
**Proof**: The color assignment *A* makes *G*_{N} edge-consistent. Along with the edge-consistency property *G*_{N} is also a forest. Hence, from theorem 1, there exists a backtrack free solution for *G*_{N} using the lists assigned. Since the list values are at most equal to , the graph *G*_{N} is -colorable and *G*_{NW} has chromatic number equal to .
This theorem has a significant impact if used in a branch and bound algorithm for finding an optimal coloring solution of a generic graph [1]. Property *P*_{1} of proposition 1 states that some lists in *N*(*W*) can have cardinality equal to one. In this case we exploit the possibility to extend the list assignment *A* fixing temporarily the colors of the nodes *iW*' *W* having a list with cardinality equal to one and deleting such color from the lists of the adjacent nodes. Let us denote with *G*_{N’} the subgraph induced by the nodes in *N*(*W'*). If some node in *N*(*W'*) has a list with cardinality equal to one then the previous task iterates until none of the nodes in *G*_{N}_{'} has a list with cardinality equal to one. If none of the lists in *G*_{N’ }is empty then the following theorem holds:
**Theorem 3**. If *G*_{N’} is a forest then *G*_{NW} has chromatic number .
**Figure 1**: A Tree Max Split graph.
If some list in *G*_{N’} becomes empty then can be augmented to '=+1 because no extension is possible, and the lists *L*_{i} obtained by the assignment *A* can be extended as *L*_{i}=*L*_{i}{'} generating lists with cardinality greater than one that is the case previously examined. In this occurrence theorem 3 can be extended to graphs having chromatic number +1.
We start our discussion on new graph classes by recalling the definition of a Split graph:
**Definition 5**. A graph is called a Split Graph SG=(*WSS*, *E*_{SG}) if it is formed by a clique *W* and a stable set SS connected by a number of edges.
Split Graphs have been studied in many papers (see [6] for an introduction) also in relation to multiprocessor scheduling models [3]. Starting from the above definition we introduce a new class of graphs:
**Definition 6**. A graph is called a Tree Max Split Graph TMSG=(*WT*, *E*_{TMSG}) if it is formed by a clique *W* and a tree *T* connected by a number of edges such that *W* is a maximum clique in TMSG.
In figure 1 Tree Max Split Graph is shown. Note that such a graph of such a class can contain cycles (i.e. is not a tree) and in particular can contain odd cycles (i.e. it is not perfect). However for any graph in this class theorems 2 and 3 hold, hence the coloring problem is polynomial. Extensions of the presented approach to other graph classes is in progress.
**References**
[1] Caramia, M., and Dell'Olmo, P., “An exact algorithm for the vertex coloring problem”, Technical Paper, University of Rome Tor Vergata, Italy, (1997). [2] Dechter, R., and Pearl, J., “Network-Based Heuristics for Constraint-Satisfaction Problems”, *Artificial Intelligence* 34 (1988) 1--38. [3] Dell'Olmo P., Speranza M.G., Tuza Z. "Comparability Graph Augmentation for some Multiprocessor Scheduling Problems", *Discrete Applied Mathematics*, 72, (1997), 71-84. [4] Freuder, E. C., “A sufficient condition of the backtrack-free search”, *J. ACM* 29 (1989) 24--32. [5] Garey, M. R., Johnson, D. S., and Stockmeyer, L., “Some simplified NP-complete graph problems”, *Theor. Comput. Sci.* 1 (1976) 237--267. [6] Golumbic, M.C., Algorithmic Graph Theory and Perfect Graphs, (Academic Press, New York, 1980). [7] Grotschel M.,Lovasz L. and Schrijver A. “*Geometrics Algorithms and Combinatorial Optimization*", Springer Verlag, New York, (1988). [8] Kratochvil, J., “Precoloring extension with fixed color bound” , *Acta Math. Univ. Comenianae* 2 (1993) 139--153. [9] Mackworth, A. K., “Consistency in networks of relations”, *Artificial Intelligence* 8 (1976) 99--118. |