Zobrazeno 1 - 10
of 75
pro vyhledávání: '"Opršal, Jakub"'
A linearly ordered (LO) $k$-colouring of a hypergraph is a colouring of its vertices with colours $1, \dots, k$ such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO $k$-colouring with a fixed number of
Externí odkaz:
http://arxiv.org/abs/2312.12981
This paper describes several cases of adjunction in the homomorphism preorder of relational structures. We say that two functors $\Lambda$ and $\Gamma$ between thin categories of relational structures are adjoint if for all structures $\mathbf A$ and
Externí odkaz:
http://arxiv.org/abs/2302.13657
A Datalog program can be viewed as a syntactic specification of a functor from database instances over some schema to database instances over another schema. The same holds more generally for $\exists$Datalog. We establish large classes of Datalog an
Externí odkaz:
http://arxiv.org/abs/2302.06366
Autor:
Dalmau, Victor, Opršal, Jakub
We study the use of local consistency methods as reductions between constraint satisfaction problems (CSPs), and promise version thereof, with the aim to classify these reductions in a similar way as the algebraic approach classifies gadget reduction
Externí odkaz:
http://arxiv.org/abs/2301.05084
Autor:
Krokhin, Andrei, Opršal, Jakub
Publikováno v:
Andrei Krokhin and Jakub Opr\v{s}al. 2022. An invitation to the promise constraint satisfaction problem. ACM SIGLOG News 9, 3 (July 2022), 30-59
The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. After a long concerted effort and many partial results, the Dichotomy Conj
Externí odkaz:
http://arxiv.org/abs/2208.13538
Autor:
Bodirsky, Manuel, Mottet, Antoine, Olšák, Miroslav, Opršal, Jakub, Pinsker, Michael, Willard, Ross
The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable if the model-complete core of the template has a pseud
Externí odkaz:
http://arxiv.org/abs/2006.12254
Publikováno v:
SIAM Journal on Computing 52(1) (2023) 38-79
The approximate graph colouring problem, whose complexity is unresolved in most cases, concerns finding a $c$-colouring of a graph that is promised to be $k$-colourable, where $c\geq k$. This problem naturally generalises to promise graph homomorphis
Externí odkaz:
http://arxiv.org/abs/2003.11351
Autor:
Krokhin, Andrei, Opršal, Jakub
Publikováno v:
Proc. 60th Ann. Symp. FOCS (2019) 1227-1239
We study the complexity of approximation on satisfiable instances for graph homomorphism problems. For a fixed graph $H$, the $H$-colouring problem is to decide whether a given graph has a homomorphism to $H$. By a result of Hell and Ne\v{s}et\v{r}il
Externí odkaz:
http://arxiv.org/abs/1904.03214
Autor:
Bodirsky, Manuel, Mottet, Antoine, Olšák, Miroslav, Opršal, Jakub, Pinsker, Michael, Willard, Ross
Publikováno v:
34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2019)
The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable when the model-complete core of the template has a pse
Externí odkaz:
http://arxiv.org/abs/1901.04237
This paper investigates the computational complexity of deciding if a given finite idempotent algebra has a ternary term operation $m$ that satisfies the minority equations $m(y,x,x) \approx m(x,y,x) \approx m(x,x,y) \approx y$. We show that a common
Externí odkaz:
http://arxiv.org/abs/1901.00316