Abstract
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 $\Omega(|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 $\Omega(|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.
Abstract (translated)
我们展示了如何将若干图论问题（例如顶点覆盖、独立集、$k$-着色）编码为CNF（合取范式），仅使用$O(|V|^2 / \lg |V|)$数量的子句，相比之下传统的编码方法需要$\Omega(|V|^2)$的数量约束。这一令人惊讶的结果是图论中ErdÅ¡os、Chung和Spencer（1983年）关于双完全子图覆盖结果的一个简单推论，并为我们理解“有限变量添加”（Manthey, Heule 和 Biere，2012年）作为预处理工具的成功提供了一个理论途径。最后，我们提出了一种新颖的编码方法，在某些密集区间图中独立集仅使用$O(|V| \lg |V|)$数量的子句（直接编码则需要$\Omega(|V|^2)$），并且这种编码已被成功应用于Bannai等人（2022年）提出的字符串压缩问题。作为直接成果，我们还得到了Mayank和Modal（2020年）提出的一个调度问题的编码大小从$O(NMT^2)$减少到$O(NMT + M T^2 \lg T)$的结果，其中$N$表示任务数量,$T$是总时间跨度，而$M$则是机器的数量。
URL
https://arxiv.org/abs/2506.14042
