Title :
Near Unanimity Constraints Have Bounded Pathwidth Duality
Author :
Barto, L. ; Kozik, M. ; Willard, R.
Author_Institution :
Math. & Stat. Dept., McMaster Univ., Hamilton, ON, Canada
Abstract :
We show that if a finite relational structure has a near unanimity polymorphism, then the constraint satisfaction problem with that structure as its fixed template has bounded pathwidth duality, putting the problem in nondeterministic logspace. This generalizes the analogous result of Dalmau and Krokhin for majority polymorphisms and lends further support to a conjecture suggested by Larose and Tesson.
Keywords :
artificial intelligence; computational complexity; constraint satisfaction problems; duality (mathematics); polymorphism; bounded pathwidth duality; constraint satisfaction problem; finite relational structure; nondeterministic logspace; unanimity constraints; unanimity polymorphism; Absorption; Algebra; Computer science; Educational institutions; Games; Standards; Vocabulary; absorption; constraint satisfaction; linear datalog; near unanimity; pathwidth duality; polymorphism;
Conference_Titel :
Logic in Computer Science (LICS), 2012 27th Annual IEEE Symposium on
Conference_Location :
Dubrovnik
Print_ISBN :
978-1-4673-2263-8
DOI :
10.1109/LICS.2012.24
