The Effect of Representations on Constraint Satisfaction Problems

Christopher Houghton

Research output: ThesisDoctoral Thesis

319 Downloads (Pure)


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 well-known 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 non-trivial 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 languageEnglish
Awarding Institution
  • Royal Holloway, University of London
  • Cohen, David, Supervisor
Award date1 Feb 2014
Publication statusUnpublished - 2013


  • Constraint Satisfaction Problems
  • Tractability
  • Structural Tractability
  • Interaction Width
  • Constraint Representations
  • SAT

Cite this