用更少的逻辑表达式编码图问题，大幅降低计算规模。
Asymptotically Smaller Encodings for Graph Problems and Scheduling
- 基于双分图覆盖理论，将图问题转为超紧凑的布尔公式。
- 顶点覆盖等经典问题仅需 $O(|V|^2 / /lg |V|)$ 条子句，远低于传统 $Ω(|V|^2)$。
- 适合研究高效约束求解、算法优化或压缩编码的读者。
我们证明，若干图问题（如顶点覆盖、独立集、$k$-着色）可被编码为仅含 $O(|V|^2 / /lg |V|)$ 条子句的合取范式（CNF），相比标准编码的 $Ω(|V|^2)$ 大幅压缩。这一结果源于 Erdős、Chung 与 Spencer（1983）关于图双分图覆盖的结论，为理解“有界变量添加”（Bounded Variable Addition）预处理技术的成功提供了理论依据。此外，我们提出一种新编码方法，对某些稠密区间图的独立集仅需 $O(|V| /lg |V|)$ 条子句（直接编码为 $Ω(|V|^2)$）。该方法已成功应用于 Bannai 等人（2022）提出的字符串压缩问题。作为直接推论，我们将 Mayank 与 Modal（2020）提出的调度问题编码规模从 $O(NMT^2)$ 降至 $O(NMT + M T^2 /lg T)$，其中 $N$ 为任务数，$T$ 为总时长，$M$ 为机器数。
原文摘要 · Abstract (English)
We show how several graph problems (e.g., vertex-cover, independent-set, $k$-coloring) can be encoded into CNF using only $O(|V|^2 / \lg |V|)$ many clauses, as opposed to the $Ω(|V|^2)$ constraints used by standard encodings. This somewhat surprising result is a simple consequence of a result of Erdős, Chung, and Spencer (1983) about biclique coverings of graphs, and opens theoretical avenues to understand the success of "Bounded Variable Addition'' (Manthey, Heule, and Biere, 2012) as a preprocessing tool. Finally, we show a novel encoding for independent sets in some dense interval graphs using only $O(|V| \lg |V|)$ clauses (the direct encoding uses $Ω(|V|^2)$), which we have successfully applied to a string-compression encoding posed by Bannai et al. (2022). As a direct byproduct, we obtain a reduction in the encoding size of a scheduling problem posed by Mayank and Modal (2020) from $O(NMT^2)$ to $O(NMT + M T^2 \lg T)$, where $N$ is the number of tasks, $T$ the total timespan, and $M$ the number of machines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。