20 citations · 75 across the 44 of their papers we have counts for
4 papers · 2 filters
Constraint Satisfaction with Counting Quantifiers
Florent Madelaine, Barnaby Martin, Juraj Stacho
We initiate the study of constraint satisfaction problems (CSPs) in the presence of counting quantifiers, which may be seen as variants of CSPs in the mould of quantified CSPs (QCS…
The Complexity of Surjective Homomorphism Problems -- a Survey
Manuel Bodirsky, Jan Kara, Barnaby Martin
We survey known results about the complexity of surjective homomorphism problems, studied in the context of related problems in the literature such as list homomorphism, retraction…
QCSP on partially reflexive forests
Barnaby Martin
We study the (non-uniform) quantified constraint satisfaction problem QCSP(H) as H ranges over partially reflexive forests. We obtain a complexity-theoretic dichotomy: QCSP(H) is e…
Low-level dichotomy for Quantified Constraint Satisfaction Problems
Barnaby Martin
Building on a result of Larose and Tesson for constraint satisfaction problems (CSP s), we uncover a dichotomy for the quantified constraint satisfaction problem QCSP(B), where B i…