Professor Andrei Krokhin's Outputs (3)

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.

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..