World's most popular travel blog for travel bloggers.

Do approximation results for CSPs hold even when domains are of finite but different size?

, , No Comments
Problem Detail: 

We need to have a precise definition for what a constraint satisfaction problem (CSP) is to study it formally. Looking at a survey by Libor Barto, titled "The Constraint Satisfaction Problem and Universal Algebra", a definition is given in Definition 2.1. Further, it is claimed this is a "standard formal definition of an instance of the CSP over a finite domain".

In particular, the definition says a CSP problem is a triple $(V,D,\mathcal{C})$, where $D$ is a finite domain. In other words, every variable takes a value from the same domain. Tracing back some earlier references from the survey, many papers define $D$ in the same way (i.e., it's the same for each variable).

I'm interested in a definition where each variable $x_i$ has a finite domain $D_i$ of size at most $k$, for some constant $k$. Surely when CSPs are defined like this, it's still NP-complete to decide whether there's a satisfying assingment, and NP-hard to maximize the number of constraints satisfied.

But: can one safely assume approximation results still hold for this definition? More generally, are there approxation results (or other algorithmic results) that break down when domains are of size at most $k$ instead of exactly the same for each variable? It feels strange the "standard formal definition" is not allowing this, so it makes me wonder if there's a reason for this limitation of generality.

Asked By : Gideon
Answered By : Yuval Filmus

This is known as multi-sorted CSPs (a sort in logic is a type of variable). See An Algebraic Approach to Multi-sorted Constraints by Bulatov and Jeavons, for example.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback