Zobrazeno 1 - 10
of 75
pro vyhledávání: '"Larose, Benoit"'
Call a finite relational structure $k$-Slupecki if its only surjective $k$-ary polymorphisms are essentially unary, and Slupecki if it is $k$-Slupecki for all $k \geq 2$. We present conditions, some necessary and some sufficient, for a reflexive digr
Externí odkaz:
http://arxiv.org/abs/2407.18167
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 unary. We prove that all reflexive cycles of girth at least 4 have this
Externí odkaz:
http://arxiv.org/abs/2206.11390
Autor:
Larose, Benoit, Markovic, Petar, Martin, Barnaby, Paulusma, Daniel, Smith, Siani, Zivny, Stanislav
Publikováno v:
ACM Trans. Comput. Log. 23(3): 14:1-14:22 (2022)
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 into a sequence of strongly connected components H_1,...,H_n so that
Externí odkaz:
http://arxiv.org/abs/2104.10570
The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, and elsewhere. Its structural and algorithmic properties have demonstrated to play a crucial role in
Externí odkaz:
http://arxiv.org/abs/1901.04398
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 undirected (partially) reflexive graphs. We introduce endo-triviality,
Externí odkaz:
http://arxiv.org/abs/1709.09486
Autor:
Chen, Hubie, Larose, Benoit
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 variables satisfying all of the constraints. One formulation of the CSP is a
Externí odkaz:
http://arxiv.org/abs/1604.00932
Publikováno v:
In Journal of Combinatorial Theory, Series B March 2021 147:37-70
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
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 problems (also known as list homomorphism problems) by A. Bulatov (2003).
Externí odkaz:
http://arxiv.org/abs/1308.0180
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 problem is either NP-complete, NL-complete, L-complete or is first-order
Externí odkaz:
http://arxiv.org/abs/0912.3802