PTAS for Sparse General-valued CSPs
PTAS for Sparse General-valued CSPs
复制标题
适用于稀疏通用价值 CSP 的 PTAS
DOI：
10.1145/3569956
复制
发表时间：
2023
影响因子：
1.3
通讯作者：
Mezei B
中科院分区：
文献类型：
--
作者：
Mezei B
我们研究约束满足问题 (CSP) 的多项式时间近似方案 (PTAS)，例如稀疏图类上的最大独立集或最小顶点覆盖。贝克的方法给出了平面图、排除次要类等的 PTAS。对于 Max-CSP，甚至更一般地，最大化有限值 CSP（其中约束是任意非负函数），Romero、Wrochna 和 Živný [SODA’21] 表明，Sherali-Adams LP 松弛为所有分数树宽脆弱类提供了一个简单的 PTAS，这是已知 PTAS 的最常见的“稀疏”条件。我们将这些结果扩展到通用的 CSP，其中包括每个可行的分配都必须满足的“清晰”（或“严格”）约束。清晰约束的唯一条件是它们的域包含一个至少与所有其他元素一样可行的元素（但可能价值较低）。为了最小化具有清晰约束的通用值 CSP，我们为所有 Bakergraph 类提供了 PTAS——Dvořák [SODA’20] 的定义，它涵盖了已知 Baker 技术适用的所有类，除了分数树宽脆弱类。虽然这是在清晰约束上满足特定单调性条件的问题的标准，但我们证明这可以放宽到对角性——与逻辑、统计物理和随机 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 that 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 allBakergraph classes—a definition by Dvořák [SODA’20] that encompasses all classes where Baker’s technique is known to work, except 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 todiagonalisability—a property of relational structures connected to logics, statistical physics, and random CSPs.