Random constraint satisfaction: Flaws and structure. (English) Zbl 0992.68193

Gent, Ian P.; Macintyre, Ewan; Prosser, Patrick; Smith, Barbara M.; Walsh, Toby

Constraints 6, No. 4, 345-372 (2001).

Summary: A recent theoretical result by D. Achlioptas, M. S. O. Molloy, L. M. Kirousis, Y. C. Stamatiou, E. Kranakis and D. Krizanc [Constraints 6, No. 4, 329-344 (2001; Zbl 0984.68085)] shows that many models of random binary constraint satisfaction problems become trivially insoluble as problem size increases. This insolubility is partly due to the presence of ‘flawed variables’, variables whose values are all ‘flawed’ (or unsupported). In this paper, we analyze how seriously existing work has been affected. We survey the literature to identify experimental studies that use models and parameters that may have been affected by flaws. We then estimate theoretically and measure experimentally the size at which flawed variables can be expected to occur. To eliminate flawed values and variables in the models currently used, we introduce a ‘flawless’ generator which puts a limited amount of structure into the conflict matrix. We prove that such flawless problems are not trivially insoluble for constraint tightnesses up to 1/2. We also prove that the standard models B and C do not suffer from flaws when the constraint tightness is less than the reciprocal of domain size. We consider introducing types of structure into the constraint graph which are rare in random graphs and present experimental results with such structured graphs.

MSC:

68T20

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Keywords:

random graphs; structured graphs

Citations:

Zbl 0984.68085