Finding a valid 3-coloring of a graph

In graph theory, the 3-colorability problem is a special case of graph coloring or graph labeling. It is a NP-complete problem. The goal is as follows: Given an undirected graph G, find an assignment of colors to the nodes out of three colorss so that no adjacent nodes have the same color. Applications of the 3-colorability problem can be found in scheduling tasks or in social networks.

Taggings:

Submitted by Thomas Linsbichler on Wed, 12/14/2011 - 09:02
1 answer

Answer Set Programming

The 3-colorablitiy problem can be solved by answer set programming (ASP), which is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems.
Given an undirected graph, for each edge from a node X to node Y you define the fact:
edge(X,Y).
The program looks as follows:

node(X) :- edge(X,Y).
node(Y) :- edge(X,Y).
col(red,X) v col(green,X) v col(blue,X) :- node(X).
:- edge(X,Y), col(C,X), col(C,Y).

With the tool DLV (http://www.dbai.tuwien.ac.at/proj/dlv/), which was developed at the University of Calabria and the Vienna University of Technology, you can compute all stable models (answer sets) of the program and thus get a valid 3-coloring of the graph.

Submitted by Thomas Linsbichler on Wed, 12/14/2011 - 09:12

Taggings: