Abstract
Constraint Satisfaction is used in the solution of a wide variety of important problems such as frequency assignment, code analysis, and scheduling. It is apparent that the modelling process is key to the success of any constraint based technique, and much work has been done on the identification of good models.
One of the key choices made during the modelling process is the selection of a constraint representation with which to express the constraints. Whilst practitioners will commonly use an implicit representation, most existing structural tractability results are defined for explicit representations. We address a wellknown anomaly in structural tractability theory, that acyclic instances are tractable when expressed explicitly, but may not be when expressed implicitly, and show that there is a link between representation and tractability.
We introduce the notion of interaction width in order to address this disconnect between theory and practice, and use this to define new tractable classes by applying existing structural tractability results to different constraint representations. We show that for a given succinct representation, a nontrivial class of instances with bounded interaction width can be transformed into an explicit representation in polynomial time so that existing structural tractability results may be applied. We compare our work to existing results for alternative succinct representations and show that the tractable classes we have defined are incomparable and novel, and can be used to derive new tractable classes for SAT.
Original language  English 

Qualification  Ph.D. 
Awarding Institution 

Supervisors/Advisors 

Award date  1 Feb 2014 
Publication status  Unpublished  2013 
Keywords
 Constraint Satisfaction Problems
 Tractability
 Structural Tractability
 Interaction Width
 Constraint Representations
 CONSTRAINTS
 SAT