论文标题
稀疏通用CSP的PTA
PTAS for Sparse General-Valued CSPs
论文作者
论文摘要
我们研究了多项式时间近似方案（PTases）的约束满意度问题（CSP），例如最大独立集或稀疏图类别的最小顶点覆盖。 贝克的方法给出了平面图，不包括少量类别的PTA。 For Max-CSPs, and even more generally, maximisation finite-valued CSPs (where constraints are arbitrary non-negative functions), Romero, Wrochna, and Živný [SODA'21] showed that the Sherali-Adams LP relaxation gives a simple PTAS for all fractionally-treewidth-fragile classes, which is the most general "sparsity" condition for which a PTAS is known.我们将这些结果扩展到了通用的CSP，其中包括“酥脆”（或“严格”）约束，这些约束必须满足每个可行的任务。清脆约束的唯一条件是它们的域中包含一个至少与其他所有元素（但可能不那么有价值）。 为了最小化具有清晰限制的通用量化的CSP，我们为所有贝克图类提供了一个PTA-Dvo红K [Soda'20]的定义涵盖了所有贝克技术可以正常工作的类别，除了可能用于分流 - treewidth-treewidth-treewidth-fragile-fragile-fragile-fragile-fragile类。尽管这是满足一定的单调性条件在清晰约束上的问题的标准，但我们表明这可以放松到对角度 - 与逻辑，统计物理学和随机CSP相关的关系结构的属性。
We study polynomial-time approximation schemes (PTASes) for constraint satisfaction problems (CSPs) such as Maximum Independent Set or Minimum Vertex Cover on sparse graph classes. Baker's approach gives a PTAS on planar graphs, excluded-minor classes, and beyond. For Max-CSPs, and even more generally, maximisation finite-valued CSPs (where constraints are arbitrary non-negative functions), Romero, Wrochna, and Živný [SODA'21] showed that the Sherali-Adams LP relaxation gives a simple PTAS for all fractionally-treewidth-fragile classes, which is the most general "sparsity" condition for which a PTAS is known. We extend these results to general-valued CSPs, which include "crisp" (or "strict") constraints that have to be satisfied by every feasible assignment. The only condition on the crisp constraints is that their domain contains an element which is at least as feasible as all the others (but possibly less valuable). For minimisation general-valued CSPs with crisp constraints, we present a PTAS for all Baker graph classes -- a definition by Dvořák [SODA'20] which encompasses all classes where Baker's technique is known to work, except possibly for fractionally-treewidth-fragile classes. While this is standard for problems satisfying a certain monotonicity condition on crisp constraints, we show this can be relaxed to diagonalisability -- a property of relational structures connected to logics, statistical physics, and random CSPs.
