A. Mottet

activity

20102026

most citedA universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP

20 citations · 85 across the 19 of their papers we have counts for

collaborators

Showing cs.CCShow all

3 papers · 1 filter

cs.CC2018

The complexity of disjunctive linear Diophantine constraints

Manuel Bodirsky, Barnaby Martin, Marcello Mamino +1

We study the Constraint Satisfaction Problem CSP(A), where A is first-order definable in (Z;+,1) and contains +. We prove such problems are either in P or NP-complete.

cs.CC2018★ 20 cited

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…

cs.CC2010★ 9 cited

Distance Constraint Satisfaction Problems

Manuel Bodirsky, Victor Dalmau, Barnaby Martin +2

We study the complexity of constraint satisfaction problems for templates $Γ$ that are first-order definable in $(Z; s u cc)$ , the integers with the successor relation. Assuming…