Paolo Dell'Olmo

Скачать 88.21 Kb.
НазваниеPaolo Dell'Olmo
Размер88.21 Kb.
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:

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:

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 X1, X2, ….., Xn and a set of n domains, D1, D2, …., Dn where each Di defines the set of values that the variable Xi 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 Xi, Xj is a subset of the Cartesian product Di Dj. 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 Xi, Xj is arc-consistent iff for any value xDi, there is a value yDj that satisfies the binary constraint between Xi and Xj.

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 X1, X2, ….., Xn 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 Xi, Xj, whenever the corresponding vertices i, jV are adjacent in G. The binary constraints are of the form {(x, y), xDi, yDj : xy }.

For the sake of simplicity we will call the node Xi as i. Defined the domains Di for each vertex iV, and substituted arcs with edges, due to the symmetry of coloring constraints, and domain Di with list Li, 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 xLi, there is a color yLj 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 GNW denote the subgraph induced by WN(W) and let GN 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 Li={1, …., } for each node iN(W); then for each Li 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 GNW, referring to the assignment A, the following properties hold:

P1: | Li | 1 for each node iN(W);

P2: if Li=Lj for adjacent nodes i, jN(W), then |LiLj| 2.

Proof: We prove the properties by contradiction. Assume |Li| = 0 for some node iN(W). Thus i has to be connected with all the nodes in W making W not maximum. Hence |Li | 1. Assume now that i and j are adjacent in GN and Li=Lj with |LiLj| =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 P1 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 |Li | 2, the subgraph GN is edge-consistent and a first result can be read out directly from theorem 1:

Theorem 2. If GN is a forest, then GNW has chromatic number .

Proof: The color assignment A makes GN edge-consistent. Along with the edge-consistency property GN is also a forest. Hence, from theorem 1, there exists a backtrack free solution for GN using the lists assigned.

Since the list values are at most equal to , the graph GN is -colorable and GNW 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 P1 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 GN’ 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 GN' has a list with cardinality equal to one. If none of the lists in GN’ is empty then the following theorem holds:

Theorem 3. If GN’ is a forest then GNW has chromatic number .

Figure 1: A Tree Max Split graph.

If some list in GN’ becomes empty then can be augmented to '=+1 because no extension is possible, and the lists Li obtained by the assignment A can be extended as Li=Li{'} 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, ESG) 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, ETMSG) 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.


[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.


Paolo Dell\ColoringCaramia M, Dell'Olmo p journal of heuristics

Paolo Dell\This book is about the work of science fiction writer Paolo Bacigalupi, and is a companion to the Paolo Bacigalupi (ology) website

Paolo Dell\Deliberazioni dell’ufficio di presidenza dell’assemblea legislativa regionale

Paolo Dell\10 Заповедей “Simplicity” от Джона Маеда
Вильям Савайа ( William Sawaya ) / Паоло Морони ( Paolo Moroni ) и Джон Маеда ( John Maeda )
Paolo Dell\Verifica dell’apprendimento

Paolo Dell\Dell'economia e delle finanze

Paolo Dell\Per le energie rinnovabili dell’Italia

Paolo Dell\La Facoltà di Economia dell’Università di Pavia 6

Paolo Dell\150° anniversario dell’unità D’italia

Paolo Dell\Presidente dell’assemblea legislativa regionale

Разместите кнопку на своём сайте:

База данных защищена авторским правом © 2014
обратиться к администрации
Главная страница