65 citations · 76 across the 6 of their papers we have counts for
5 papers · 1 filter
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…
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…