65 citations · 76 across the 6 of their papers we have counts for
8 papers
Surjective polymorphisms of reflexive cycles
Isabelle Larivière, Benoit Larose, David Emmanuel Pazmiño Pullas
A reflexive cycle is any reflexive digraph whose underlying undirected graph is a cycle. Call a relational structure Slupecki if its surjective polymorphisms are all essentially un…
QCSP on Reflexive Tournaments
Benoit Larose, Petar Markovic, Barnaby Martin +3
We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split…
Dismantlability, connectedness, and mixing in relational structures
Raimundo Briceño, Andrei Bulatov, Victor Dalmau +1
The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, and elsewhere. Its structural…
Surjective H-Colouring over Reflexive Digraphs
Benoit Larose, Barnaby Martin, Daniel Paulusma
The Surjective H-Colouring problem is to test if a given graph allows a vertex-surjective homomorphism to a fixed graph H. The complexity of this problem has been well studied for…
Asking the metaquestions in constraint tractability
Hubie Chen, Benoit Larose
The constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, whether or not there is an assignment to the variab…
Space complexity of list H-colouring: a dichotomy
Laszlo Egri, Pavol Hell, Benoit Larose +1
The Dichotomy Conjecture for constraint satisfaction problems (CSPs) states that every CSP is in P or is NP-complete (Feder-Vardi, 1993). It has been verified for conservative prob…
The complexity of the list homomorphism problem for graphs
Laszlo Egri, Andrei Krokhin, Benoit Larose +1
We completely classify the computational complexity of the list H-colouring problem for graphs (with possible loops) in combinatorial and algebraic terms: for every graph H the pro…
A Characterisation of First-Order Constraint Satisfaction Problems
Benoit Larose, Cynthia Loten, Claude Tardif
We describe simple algebraic and combinatorial characterisations of finite relational core structures admitting finitely many obstructions. As a consequence, we show that it is dec…