Algebra Seminar talk
2018-10-25 (10:15)
Jakub Opršal (TU Dresden)
A few algorithms for promise constraint satisfaction
Abstract:
Since deciding whether a given graph is 3-colorable is NP-complete, and
checking validity of a coloring is an easy problem, also the problem of
finding a coloring of a 3-colorable graph with 3 colors is a well-known
NP-complete.
One might be interested in a relaxed version of this problem, e.g. finding a coloring of a 3-colorable graph that uses k colors for some fixed k > 3. This falls into a more general scope of so-called promise constraint satisfaction problem (PCSP): A template of PCSP is a pair of relational structures A and B with a homomorphism from A to B. The goal is, given a similar structure that maps homomorphically to A, find a homomorphism to B. (The existence of a homomorphism to A is the aforementioned promise.)
The talk will present basics of the algebraic theory behind complexity of PCSPs, and how to use tractability results from the CSP to obtain new tractability results for PCSPs.
This is a joint work with J. Bulín and A. Krokhin.