Abstract
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 \(\text{MaxPCSP}(G,H)\) : Given an input (multi)graph \( X \) that admits a map to \( G \) preserving a \(\rho\) -fraction of the edges, find a map from \( X \) to \( H \) that preserves a \(\rho\) -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 \(\rho\) 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\rho\) edges, thus improving on the subgraph with \(0.878\rho\) edges obtained by the classic Max-Cut algorithm of Goemans and Williamson.
Funding Information
  • UKRI (EP/X024431/1)
  • Clarendon Fund Scholarship

This publication has 40 references indexed in Scilit: