Deterministic and randomized approaches to constraint satisfaction problems

Abstract

Tutor: Victor Dalmau

Treball de fi de grau en Enginyeria Matemàtica en Ciència de Dades

This thesis explores algorithmic approaches to solving Constraint Satisfaction Problems (CSPs), with a particular focus on randomized algorithms. The study targets CSP instances that combine three specific classes of constraints: Value Restriction Constraints, 2-Fan Constraints, and Binary Permutation Constraints. These form one of the largest known tractable fragments of the general binary CSP landscape. To build a solid foundation, the thesis first introduces these constraint families and develops deterministic algorithms for each, gaining deeper insights into their structural properties. The core contribution is the design and analysis of a general randomized algorithm that solves combined instances of these constraints with polynomial expected runtime. Inspired by techniques such as Papadimitriouasˆ random walk for 2-SAT, this approach demonstrates how randomization can effectively find a solution for such CSPs. The results align with and extend prior theoretical work on tractable CSP classes, providing an algorithmic solution for this important subclass of problems.

Aquesta tesi explora algoritmes per a la resolucio de Problemes de Satisfacció de Restriccions (CSP), amb un emfasi particular en els algoritmes randomitzats. L’estudi es centra en instancies de CSP que combinen tres classes especıfiques de restriccions: restriccions de valor (Value Restriction Constraints), restriccions 2-Fan i restriccions de permutacio binaria (Binary Permutation Constraints). Aquestes constitueixen un dels fragments tractables mes coneguts dins del panorama general dels CSP binaris. Per establir una base solida, la tesi introdueix primer aquestes famílies de restriccions i desenvolupa algoritmes deterministes per a cadascuna, aprofundint en la comprensio de les seves propietats estructurals. La contribució principal consisteix en el disseny i l’analisi d’un algoritme randomitzat general que resol instancies combinades d’aquestes restriccions amb un temps esperat d’execució polinomic. Inspirat en tècniques com l’algoritme de Papadimitriou per al problema 2-SAT, aquest algoritme demostra com l’aleatoritzacio pot trobar solucions de ́manera efectiva per a aquest tipus de CSP. Els resultats s’alineen amb els treballs teorics previs sobre classes tractables de CSP, i aporten una solucio algorítmica per a aquest important subconjunt de problemes.