In this thesis I study constraint satisfaction problems or CSPs. These require determining whether values can be assigned to variables so that all constraints are satisfied. An important challenge is to identify tractable CSPs which can be solved efficiently. CSP instances have usually been grouped together by restricting either the allowed combinations of values, or the way the variables are allowed to interact. Such restrictions sometimes yield tractable CSPs. A weakness of this method is that it cannot explain why all-different constraints form a tractable CSP. In this common type of constraint, all variables must be assigned values that are different from each other. New techniques are therefore needed to explain why such CSPs can be solved efficiently. My main contribution is an investigation of such hybrid CSPs which cannot be defined with either one of these kinds of restrictions. The main technique I use is a transformation of a CSP instance to the microstructure representation. This represents an instance as a collection of sets, and a solution of the instance corresponds to an independent set in the clause structure. For the common case where all constraints involve only two variables, I show how the microstructure can be used to define CSPs that are tractable because their clause structures fall within classes of graphs for which an independent set of specified size can be found efficiently. Such tractable hereditary classes are defined by using the technique of excluded induced subgraphs, such as classes of graphs that contain neither odd cycles with five or more vertices, nor their complements. I also develop finer grained techniques, by allowing vertices of the microstructure representation to be assigned colours, and the variables to be ordered. I show that these techniques define a new tractable CSP that forbids an ordered vertex-coloured subgraph in the microstructure representation.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:627773 |
| Date | January 2013 |
| Creators | Salamon, András Z. |
| Contributors | Jeavons, Peter G. |
| Publisher | University of Oxford |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://ora.ox.ac.uk/objects/uuid:5d641fff-4d95-43b2-9ff8-73395d782ad8 |
Page generated in 0.0017 seconds