Open Collections

A study on generalized solution concepts in constraint satisfaction and graph colouring

University of British Columbia

The concept of super solutions plays a crucial role in using the constraint satisfaction framework to model many AI problems under uncertain, dynamic, or interactive environments. The availability of large-scale, dynamic, uncertain, and networked data sources in a variety of application domains provides a challenge and opportunity for the constraint programming community, and we expect that super solutions will continue to attract a great deal of interest. In the first part of this thesis, we study the probabilistic behaviour of super solutions of random instances of Boolean Satisability (SAT) and Constraint Satisfaction Problems (CSPs). Our analysis focuses on a special type of super solutions, the (1,0)-super solutions. For random k-SAT, we establish the exact threshold of the phase transition of the solution probability for the cases of k = 2 and 3, and we upper and lower bound the threshold of the phase transition for the case of k ≥ 4. For random CSPs, we derive a non-trivial upper bound on the threshold of phase transitions. Graph colouring is one of the most well-studied problems in graph theory. A solution to a graph colouring problem is a colouring of the vertices such that each colour class is a stable set. A relatively new generalization of graph colouring is cograph colouring, where each colour class is a cograph. Cographs are the minimum family of graphs containing a single vertex and are closed under complementation and disjoint union. We define the cogchromatic number of a graph G as the minimum number of colours needed by a cograph colouring of G. Several problems related to cograph colouring are studied in the second part of this thesis, including properties of graphs that have cog-chromatic number 2; computational hardness of deciding and approximating the cog-chromatic number of graphs; and graphs that are critical in terms of cog-chromatic numbers. Several interesting constructions of graphs with extremal properties with respect to cograph colouring are also presented.

Text

2014-08-19

Attribution-NonCommercial-NoDerivs 2.5 Canada

http://hdl.handle.net/2429/50022

Interdisciplinary Studies

University of British Columbia

UBCO

http://creativecommons.org/licenses/by-nc-nd/2.5/ca/