Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-040 | 4th November 2020 16:17

Topology and adjunction in promise constraint satisfaction

RSS-Feed




Revision #1
Authors: Andrei Krokhin, Jakub Opršal, Marcin Wrochna, Stanislav Zivny
Accepted on: 4th November 2020 16:17
Downloads: 276
Keywords: 


Abstract:

The approximate graph colouring problem concerns colouring a $k$-colourable graph with $c$ colours, where $c\geq k$. This problem naturally generalises to promise graph homomorphism and further to promise constraint satisfaction problems. Complexity analysis of all these problems is notoriously difficult. In this paper, we introduce two new techniques to analyse 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 NP-hardness results for a significant class of approximate graph colouring and promise graph homomorphism problems.



Changes to previous version:

Corrected a mistakes in the proof of Theorem 1.9 and reformulated Lemma 3.26.


Paper:

TR20-040 | 25th March 2020 20:07

Topology and adjunction in promise constraint satisfaction


Abstract:

The approximate graph colouring problem concerns colouring a $k$-colourable
graph with $c$ colours, where $c\geq k$. This problem naturally generalises
to promise graph homomorphism and further to promise constraint satisfaction
problems. Complexity analysis of all these problems is notoriously difficult.
In this paper, we introduce two new techniques to analyse 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 NP-hardness results for a significant class of approximate
graph colouring and promise graph homomorphism problems.



ISSN 1433-8092 | Imprint