There are no pure relational width 2 constraint satisfaction problems |
| |
| Authors: | Ví ctor Dalmau |
| |
| Affiliation: | Departament de tecnologies de la informació i les comunicacions, Universitat Pompeu Fabra, Estació de França, Passeig de la circumval.lació 8, 08003 Barcelona, Spain |
| |
| Abstract: | In this note, we show that every constraint satisfaction problem that has relational width 2 has also relational width 1. This is achieved by means of an obstruction-like characterization of relational width which we believe to be of independent interest. |
| |
| Keywords: | Computational complexity Constraint satisfaction problems |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
