On the Complexity of Some Valued Constraint Satisfaction Problems

Hannes Uppman ( Linköping University )

Many combinatorial optimization and feasibility problems can be expressed as a valued constraint satisfaction problem (VCSP). The VCSPs include for example every constraint satisfaction problem (e.g. 3-SAT) and every maximum constraint satisfaction problem (e.g. Max-Cut). Recently a complete characterization of all finite-valued VCSPs that can be solved in polynomial-time (assuming P != NP) has been obtained [Thapper-Zivny FOCS'12, Kolmogorov ICALP'13, Thapper-Zivny STOC'13]. However, VCSPs that are not finite-valued are less understood. In this talk I will present work on the complexity of a particular type of VCSPs known as extended minimum cost homomorphism problems. These are VCSPs that in some sense may be thought of as "far from finite-valued".

We will focus especially on a subclass of the extended minimum cost homomorphism problems that for example contains every minimum solution problem. For any problem (on any finite domain) in this class we will see that one can either prove NP-hardness or the existence of quite a lot of "useful structure" in the instances of the problem. We apply this to prove a dichotomy on small domains.