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...
Main Authors: | Krokhin, A, Oprsal, J, Wrochna, M, Zivny, S |
---|---|
Format: | Journal article |
Language: | English |
Published: |
Society for Industrial and Applied Mathematics
2023
|
Similar Items
-
The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
by: Brakensiek, J, et al.
Published: (2020) -
The constraint satisfaction problem: complexity and approximability
by: Krokhin, A, et al.
Published: (2017) -
Binarisation for Valued Constraint Satisfaction Problems
by: Cohen, D, et al.
Published: (2016) -
Binarisation for valued constraint satisfaction problems
by: Cohen, D, et al.
Published: (2017) -
Binary constraint satisfaction problems defined by excluded topological minors
by: Cohen, D, et al.
Published: (2018)