Dalmau, V. and Krokhin, A. (2008) 'Majority constraints have bounded pathwidth duality.', European journal of combinatorics., 29 (4). pp. 821-837.
Abstract
We study certain constraint satisfaction problems which are the problems of deciding whether there exists a homomorphism from a given relational structure to a fixed structure with a majority polymorphism. We show that such a problem is equivalent to deciding whether the given structure admits a homomorphism from an obstruction belonging to a certain class of structures of bounded pathwidth. This implies that the constraint satisfaction problem for any fixed structure with a majority polymorphism is in NL.
| Item Type: | Article |
|---|---|
| Full text: | Full text not available from this repository. |
| Publisher Web site: | http://dx.doi.org/10.1016/j.ejc.2007.11.020 |
| Date accepted: | No date available |
| Date deposited: | No date available |
| Date of first online publication: | May 2008 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
