Zobrazeno 1 - 10
of 126
pro vyhledávání: '"KROKHIN, ANDREI"'
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
The 1-in-3 and Not-All-Equal satisfiability problems for Boolean CNF formulas are two well-known NP-hard problems. In contrast, the promise 1-in-3 vs. Not-All-Equal problem can be solved in polynomial time. In the present work, we investigate this co
Externí odkaz:
http://arxiv.org/abs/2302.03456
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
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
Publikováno v:
J. ACM 68, 4, Article 28 (July 2021), 66 pages
The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the last 20 years. A new version of the CSP, the promise CSP (PCSP) has recently been proposed, motivated by open questions about the appro
Externí odkaz:
http://arxiv.org/abs/1811.00970
Autor:
Krokhin, Andrei, Marx, Dániel
We study the complexity of local search for the Boolean constraint satisfaction problem (CSP), in the following form: given a CSP instance, that is, a collection of constraints, and a solution to it, the question is whether there is a better (lighter
Externí odkaz:
http://arxiv.org/abs/1711.03894
In this paper we study the approximability of (Finite-)Valued Constraint Satisfaction Problems (VCSPs) with a fixed finite constraint language {\Gamma} consisting of finitary functions on a fixed finite domain. An instance of VCSP is given by a finit
Externí odkaz:
http://arxiv.org/abs/1610.01019
Autor:
Cohen, David A., Cooper, Martin C., Jeavons, Peter G., Krokhin, Andrei, Powell, Robert, Zivny, Stanislav
Publikováno v:
SIAM Journal on Discrete Mathematics 31(4) (2017) 2279-2300
We study methods for transforming valued constraint satisfaction problems (VCSPs) to binary VCSPs. First, we show that the standard dual encoding preserves many aspects of the algebraic properties that capture the computational complexity of VCSPs. S
Externí odkaz:
http://arxiv.org/abs/1608.01628
Autor:
Dalmau, Víctor, Kozik, Marcin, Krokhin, Andrei, Makarychev, Konstantin, Makarychev, Yury, Opršal, Jakub
An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimiz
Externí odkaz:
http://arxiv.org/abs/1607.04787