20 citations · 34 across the 12 of their papers we have counts for
6 papers · 1 filter
On guarded extensions of MMSNP
Alexey Barsukov, Florent R. Madelaine
Feder and Vardi showed that the class Monotone Monadic SNP without inequality (MMSNP) has a P vs NP-complete dichotomy if and only if such a dichotomy holds for finite-domain Const…
The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation
Catarina Carvalho, Florent Madelaine, Barnaby Martin +1
Let A be an idempotent algebra on a finite domain. By mediating between results of Chen and Zhuk, we argue that if A satisfies the polynomially generated powers property (PGP) and…
A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
Manuel Bodirsky, Florent Madelaine, Antoine Mottet
The logic MMSNP is a restricted fragment of existential second-order logic which allows to express many interesting queries in graph theory and finite model theory. The logic was i…
From complexity to algebra and back: digraph classes, collapsibility and the PGP
Catarina Carvalho, Florent Madelaine, Barnaby Martin
Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idempotent polymorphisms of certain digraph classes. Our fir…
QCSP on partially reflexive cycles - the wavy line of tractability
Florent Madelaine, Barnaby Martin
We study the (non-uniform) quantified constraint satisfaction problem QCSP(H) as H ranges over partially reflexive cycles. We obtain a complexity-theoretic dichotomy: QCSP(H) is ei…
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…