Abstract
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 problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems.
| Original language | English |
|---|---|
| Pages (from-to) | 38-79 |
| Number of pages | 42 |
| Journal | SIAM Journal on Computing |
| Volume | 52 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 14 Feb 2023 |
Bibliographical note
Funding:This project has received funding from the European Research Council (ERC) underthe European Union's Horizon 2020 research and innovation programme (grant agreement 714532).The first and second authors were supported by the UK EPSRC grant EP/R034516/1. The fourthauthor was supported by a Royal Society University Research Fellowship. The paper reflects onlythe authors' views and not the views of the ERC or the European Commission. The European Unionis not liable for any use that may be made of the information contained therein.
Keywords
- graph coloring
- graph homomorphism problem
- constraint satisfaction
- polymor-phism
- promise problem