无二分图的最大 k-权重满意度与最大覆盖的参数近似方案

带基数约束的最大满意度问题（CC-Max-Sat）是经典的 NP 完全问题之一，它泛化了最大覆盖、部分顶点覆盖、带二分约束的 Max-2-SAT，并在所有算法范式中得到了广泛研究。在这个问题中，我们给定一个 CNF 公式 \ (\) 和一个正整数 \ (k\)，目标是找到一个赋值 \ (\)，使得至多有 \ (k\) 个变量被设置为真（也称为 \ (k\) -权重赋值），从而最大化 \ (\) 满足的子句数量。已知该问题允许一个近似算法，其因子为 \ (1-1e\)，可能是最优的。此外，假设间隙指数时间假设（Gap-ETH），对于任何 \ (>0\) 和任何函数 \ (h\)，没有 \ (h (k) (n+m) ^o (k) \) 时间算法可以在 \ (n\) 个元素和 \ (m\) 个集合的最大覆盖（CC-Max-Sat 的单调版本）中找到比例在 \ ( (1-1e+) \) 以内，即使承诺存在 \ (k\) 个集合完全覆盖整个宇宙。事实上，假设独特游戏猜想，即使输入公式是 \ (2\) -CNF，该问题在 \ (0. 929\) 以内也难以近似。这些难以处理的结果促使我们探索可以绕过这些障碍的公式家族。为此，我们考虑 \ (K₃, ₃\) -无公式（即，公式的子句-变量发生二部图不包含 \ (K₃, ₃\) 作为诱导子图）。我们证明，对于每个 \ (>0\)，存在一个用于 \ (K₃, ₃\) -无公式的 CC-Max-Sat 算法，其近似比为 \ ( (1-) \)，且运行时间为 \ (2^O ( (dk{) ^d) } (n+m) ^O (1) \) （这些算法称为 FPT-AS）。对于 \ (K₃, ₃\) -无集合族的最大覆盖，我们获得了 FPT-AS，运行时间为 \ ( (dk) ^O (dk) n^O (1) \)。我们的第二个结果考虑“优化 \ (k\) ”，在最大覆盖问题的固定覆盖约束下。为了说明我们的结果，我们首先将最大覆盖问题重新表述为带覆盖约束的最大红蓝主导集问题。这里，输入是一个二部图 \ (G= (A, B, E) \)，一个正整数 \ (t\)，目标是寻找一个最小大小的子集 \ (S A\)，使得 \ (|N (S) |\)（\ (S\) 的邻居集合的大小）至少为 \ (t\)。我们设计了一个在 \ (K₃, ₃\) -无二部图上的带覆盖约束的最大红蓝主导集的附加近似算法，运行时间为 FPT。特别是，如果 \ (k\) 表示 \ (S A\) 的最小大小，以使 \ (|N (S) | t\)，则我们的算法的运行时间为 \ ( (kd) ^O (kd) n^O{ (1) }\)，并返回一个集合 \ (S^\)，使得 \ (|N (S^) | t\) 且 \ (|S^| k+1\)。这与我们的一个问题的特例，即部分顶点覆盖问题（或最大 \ (k\) -VC）是 W1-困难的这一事实形成鲜明对比。因此，我们为最大覆盖问题在 \ (K₃, ₃\) -无二部图上获得了最佳可能的参数近似算法。