AAAI Publications, Tenth Symposium of Abstraction, Reformulation, and Approximation

Font Size: 
Microstructures for CSPs with Constraints of Arbitrary Arity
Achref El Mouelhi, Philippe Jégou, Cyril Terrioux

Last modified: 2013-06-19


Many works have studied the properties of CSPs which are based on the structures of constraint networks, or based on the features of compatibility relations. Studies on structures rely generally on properties of graphs for binary CSPs and on properties of hypergraphs for the general case, that is CSPs with constraints of arbitrary arity. In the second case, using the dual representation of hypergraphs, that is a reformulation of the instances, we can exploit notions and properties of graphs. For the studies of compatibility relations, the exploitation of properties of graphs is possible studying a graph called microstructure which allows to reformulate instances of binary CSP. Unfortunately, this approach is limited to CSPs with binary constraints. In this paper, we propose theoretical tools based on graphs to represent microstructures for the general case. This approach avoids to exploit directly hypergraphs, even if the microstructure based on hypergraphs has already been mentioned in (Cohen 2003). The advantage of such an approach is that the literature of Graph Theory is really more extended than one of Hypergraph Theory. Thus the theoretical results and efficient algorithms are more numerous, offering a larger number of existing tools which can be operated. We introduce here three possible definitions of microstructures based on graphs. We show how these representations can form new theoretical tools to generalize a number of results already obtained on binary CSPs. We think that these representations should be of interest for the community, firstly for the generalization of existing results, but also to obtain original results for CSPs with constraints of arbitrary arity.


Constraint Satisfaction Problems; Graph representation; Tractable classes

Full Text: PDF