Topology and adjunction in promise constraint satisfaction

Topology and adjunction in promise constraint satisfaction

The approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable, where c≥k. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction probl...

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron:	Krokhin, A, Oprsal, J, Wrochna, M, Zivny, S
Fformat:	Journal article
Iaith:	English
Cyhoeddwyd:	Society for Industrial and Applied Mathematics 2023

Eitemau Tebyg

The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
gan: Brakensiek, J, et al.
Cyhoeddwyd: (2020)

The constraint satisfaction problem: complexity and approximability
gan: Krokhin, A, et al.
Cyhoeddwyd: (2017)

Binarisation for valued constraint satisfaction problems
gan: Cohen, D, et al.
Cyhoeddwyd: (2017)

Binary constraint satisfaction problems defined by excluded topological minors
gan: Cohen, D, et al.
Cyhoeddwyd: (2018)

The complexity of promise SAT on non-Boolean domains
gan: Brandts, A, et al.
Cyhoeddwyd: (2020)

The complexity of promise SAT on non-Boolean domains
gan: Brandts, A, et al.
Cyhoeddwyd: (2021)

The complexity of soft constraint satisfaction
gan: Cohen, D, et al.
Cyhoeddwyd: (2006)

The complexity of soft constraint satisfaction
gan: Cohen, D, et al.
Cyhoeddwyd: (2006)

The complexity of valued constraint satisfaction problems
gan: Živný, S
Cyhoeddwyd: (2012)

Constraint satisfaction problems and finite algebras
gan: Bulatov, A, et al.
Cyhoeddwyd: (2000)

Constraint satisfaction problems and finite algebras
gan: Bulatov, A, et al.
Cyhoeddwyd: (2000)

The Complexity of Constraint Satisfaction: An Algebraic Approach
gan: Krokhin, A, et al.
Cyhoeddwyd: (2004)

Constraint satisfaction problems on intervals and lengths
gan: Krokhin, A, et al.
Cyhoeddwyd: (2004)

Constraint satisfaction problems on intervals and lengths
gan: Krokhin, A, et al.
Cyhoeddwyd: (2004)

Promise constraint satisfaction problems
gan: Brandts-Longtin, A
Cyhoeddwyd: (2022)

1-in-3 vs. not-all-equal: dichotomy of a broken promise
gan: Ciardo, L, et al.
Cyhoeddwyd: (2025)

1-in-3 vs. not-all-equal: dichotomy of a broken promise
gan: Ciardo, L, et al.
Cyhoeddwyd: (2024)

The complexity of constraint satisfaction games and QCSP
gan: Boerner, F, et al.
Cyhoeddwyd: (2009)

The complexity of constraint satisfaction games and QCSP
gan: Börner, F, et al.
Cyhoeddwyd: (2009)

Supermodularity on chains and complexity of maximum constraint satisfaction
gan: Vladimir Deineko, et al.
Cyhoeddwyd: (2005-01-01)

Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey
gan: Krokhin, A, et al.
Cyhoeddwyd: (2003)

Functions of multiple−valued logic and the complexity of constraint satisfaction: A short survey
gan: Krokhin, A, et al.
Cyhoeddwyd: (2003)

Improved hardness for H-colourings of G-colourable graphs
gan: Wrochna, M, et al.
Cyhoeddwyd: (2020)

The complexity of general-valued constraint satisfaction problems seen from the other side
gan: Carbonnel, C, et al.
Cyhoeddwyd: (2022)

Variable and value elimination in binary constraint satisfaction via forbidden patterns
gan: Cohen, DA, et al.
Cyhoeddwyd: (2015)

Pliability and approximating max-CSPs
gan: Romero, M, et al.
Cyhoeddwyd: (2023)

Nanoparticles: A promising novel adjunct for dentistry
gan: Jagat Bhushan, et al.
Cyhoeddwyd: (2019-01-01)

Treewidth-pliability and PTAS for Max-CSPs
gan: Romero, M, et al.
Cyhoeddwyd: (2021)

PTAS for sparse general-valued CSPs
gan: Mezei, B, et al.
Cyhoeddwyd: (2023)

PTAS for sparse general-valued CSPs
gan: Mezei, BF, et al.
Cyhoeddwyd: (2021)

Island Constraints and Adjunct & Argument Asymmetry in Turkish
gan: Sinan Çakır
Cyhoeddwyd: (2016-12-01)

The complexity of maximal constraint languages
gan: Bulatov, A, et al.
Cyhoeddwyd: (2001)

The complexity of maximal constraint languages
gan: Bulatov, A, et al.
Cyhoeddwyd: (2001)

The complexity and expressive power of valued constraints
gan: Zivny, S
Cyhoeddwyd: (2009)

The Complexity and Expressive Power of Valued Constraints
gan: Živný, S
Cyhoeddwyd: (2009)

Soft constraints: Complexity and multimorphisms
gan: Cohen, D, et al.
Cyhoeddwyd: (2003)

Soft constraints: complexity and multimorphsims
gan: Cohen, D, et al.
Cyhoeddwyd: (2003)

Tractable valued constraints
gan: Jeavons, P, et al.
Cyhoeddwyd: (2012)

Expressibility of valued constraints
gan: Živný, S, et al.
Cyhoeddwyd: (2007)

Tractable Valued Constraints
gan: Jeavons, P, et al.
Cyhoeddwyd: (2013)