A Dichotomy for Maximum PCSPs on Graphs

Fix two non-empty loopless graphs \(G\) and \(H\) such that \(G\) maps homomorphically to \(H\) . The Maximum Promise Constraint Satisfaction Problem parameterised by \(G\) and \(H\) is the following computational problem, denoted by \({MaxPCSP}(G,H)\) : Given an input (multi)graph \(X\) that admits a map to \(G\) preserving a \(ρ\) -fraction of the edges, find a map from \(X\) to \(H\) that preserves a \(ρ\) -fraction of the edges. As our main result, we give a complete classification of this problem under Khot's Unique Games Conjecture: The only tractable cases are when \(G\) is bipartite and \(H\) contains a triangle. Along the way, we establish several results, including an efficient approximation algorithm for the following problem: Given a (multi)graph \(X\) which contains a bipartite subgraph with \(ρ\) edges, what is the largest triangle-free subgraph of \(X\) that can be found efficiently? We present an SDP-based algorithm that finds one with at least \(0.8823ρ\) edges, thus improving on the subgraph with \(0.878ρ\) edges obtained by the classic Max-Cut algorithm of Goemans and Williamson.