Brakensiek–Guruswami's approximate graph homomorphism hardness conjecture

Let A\mathbf{A} and B\mathbf{B} be non-bipartite loopless undirected graphs such that AB\mathbf{A}\to\mathbf{B}. The Brakensiek–Guruswami conjecture asserts that

PCSP(A,B)\operatorname{PCSP}(\mathbf{A},\mathbf{B})

is NP\operatorname{NP}-hard. Here PCSP(A,B)\operatorname{PCSP}(\mathbf{A},\mathbf{B}) is the approximate graph homomorphism problem distinguishing instances homomorphic to A\mathbf{A} from instances not homomorphic to B\mathbf{B}. This is presented as a stronger conjecture than the approximate graph-colouring conjecture; the source identifies graphs with loops or bipartite graphs as trivial or reducible to 22-colouring, while the stated non-bipartite loopless case remains open.

Sources & referencesView supporting material

Primary source

Lorenzo Ciardo and Stanislav Živný, “Semidefinite programming and linear equations vs. homomorphism problems”, arXiv:2311.00882 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.