Constraint Satisfaction Parameterized by Solution Size

DOI10.1137/120882160zbMath1360.68499arXiv1206.4854OpenAlexW2569790754MaRDI QIDQ5494930

Andrei A. Bulatov, Dániel Marx

Publication date: 30 July 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1206.4854

zbMATH Keywords

constraint satisfactionparameterized complexityglobal constraintsmultivalued morphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Tractability in constraint satisfaction problems: a survey ⋮ Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction

This page was built for publication: Constraint Satisfaction Parameterized by Solution Size