CSP duality and trees of bounded pathwidth.

Carvalho, C.; Dalmau, V.; Krokhin, A.

doi:10.1016/j.tcs.2010.05.016

All Outputs (4)

Retractions to pseudoforests. (2010)
Journal Article
Feder, T., Hell, P., Jonsson, P., Krokhin, A., & Nordh, G. (2010). Retractions to pseudoforests. SIAM Journal on Discrete Mathematics, 24(1), 101-112. https://doi.org/10.1137/080738866

On the hardness of losing weight (2010)
Journal Article
Krokhin, A., & Marx, D. (online). On the hardness of losing weight. https://doi.org/10.1007/978-3-540-70575-8_54

We study the complexity of local search for the Boolean constraint satisfaction problem (CSP), in the following form: given a CSP instance, that is, a collection of constraints, and a solution to it, the question is whether there is a better (lighter... Read More about On the hardness of losing weight.

The complexity of the list homomorphism problem for graphs. (2010)
Presentation / Conference Contribution
Egri, L., Krokhin, A., Larose, B., & Tesson, P. (2010, December). The complexity of the list homomorphism problem for graphs. Presented at Symposium on Theoretical Aspects of Computer Science., Nancy, France

CSP duality and trees of bounded pathwidth. (2010)
Journal Article
Carvalho, C., Dalmau, V., & Krokhin, A. (2010). CSP duality and trees of bounded pathwidth. Theoretical Computer Science, 411(34-36), 3188-3208. https://doi.org/10.1016/j.tcs.2010.05.016

We study non-uniform constraint satisfaction problems definable in monadic Datalog stratified by the use of non-linearity. We show how such problems can be described in terms of homomorphism dualities involving trees of bounded pathwidth and in algeb... Read More about CSP duality and trees of bounded pathwidth..