Silvia Butti

The Complexity of the Distributed Constraint Satisfaction Problem

I will present some recent work with Victor Dalmau on the complexity of the Distributed Constraint Satisfaction Problem (DCSP). We study the DCSP on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which communicate with each other by sending messages through fixed communication channels. Our results endorse the well-known fact from classical CSPs that the complexity of fixed template computational problems depends on the template’s polymorphisms. Specifically, we show that \(\textnormal{DCSP}(\Gamma)\) is polynomial-time tractable if and only if \(\Gamma\) is invariant under symmetric polymorphisms of all arities. Otherwise, there are no algorithms that solve \(\textnormal{DCSP}(\Gamma)\) in finite time.

I will discuss the proof of this dichotomy while establishing a tight connection between the basic LP relaxation of a CSP and the well-known concept of iterated degree from graph theory, which we extend to CSPs.