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 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.
From: Stanislav Živný [view email]
[v1]
Fri, 28 Jun 2024 17:27:54 UTC (25 KB)
[v2]
Tue, 22 Oct 2024 22:48:59 UTC (26 KB)
[v3]
Wed, 18 Jun 2025 08:15:56 UTC (36 KB)
[v4]
Sun, 1 Mar 2026 21:29:19 UTC (38 KB)
[v5]
Fri, 7 Aug 2026 14:33:33 UTC (38 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。