A Dichotomy for Maximum PCSPs on Graphs
Open Access
- 5 October 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (4) , 1-30
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.
Keywords
All Related Versions
Funding Information
- UKRI (EP/X024431/1)
- Clarendon Fund Scholarship
This publication has 40 references indexed in Scilit:
- Hardness of Finding Independent Sets in Almost 3-Colorable Graphs2010
- How to Round Any CSP2009
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSPRandom Structures & Algorithms, 2008
- The Hardness of 3-Uniform Hypergraph ColoringCombinatorica, 2005
- Derandomization of Dimensionality Reduction and SDP Based AlgorithmsLecture Notes in Computer Science, 2005
- On the algebraic structure of combinatorial problemsTheoretical Computer Science, 1998
- Improved approximation algorithms for MAXk-CUT and MAX BISECTIONAlgorithmica, 1997
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- On the complexity of H-coloringJournal of Combinatorial Theory, Series B, 1990
- Reducibility among Combinatorial Problems1972