2-SAT 问题总结

一直以来对 2-SAT 的理解比较模糊,所以写这样一个尽可能清晰的总结来理清思路。

2-SAT 问题的定义:有 \(n\) 个逻辑变量,用 \(b_i\) 表示第 \(i\) 个逻辑变量。\(m\) 个限制条件,每一个限制条件形如:\((\neg)b_i \to (\neg) b_j\)。问是否存在满足限制的 \(b\)

用图来描述限制条件。对每个逻辑变量建两个点,分别代表取值为 \(0\) 和取值为 \(1\)。代表 \(b_i=0\) 的点为 \(p_i\),代表 \(b_i = 1\) 的点为 \(q_i\)。对每个限制条件,在图上连一条有向边,表示一个命题推出另一个命题,然后再加一条边表示该限制条件的逆否命题。举例来说,如果有限制条件 \(\neg b_i \rightarrow b_j\),就加入 \((p_i, q_j)\)\((p_j, q_i)\) 这两条有向边。问题就变为判定是否存在对于任意的 \(i\),恰好包含 \(p_i\)\(q_i\) 中的一个点的闭合子图。

定理:2-SAT 有解的充要条件是,对于任意的 \(i\)\(p_i\)\(q_i\) 不在同一强连通分量中。

必要性是显然的。

下面用构造证明充分性:

先 tarjan 求出强连通分量,把每个强联通分量缩成一个点。由于一个强连通分量内的点对应相反取值的点也构成一个强连通分量,所以缩点后,这个问题变为了一个更小的 2-SAT 问题。只需要解决图是 DAG 时的问题即可。

把所有的边方向反过来。下面所有的讨论都是在反图上的。

用符号 \(v^r\) 表示与点 \(v\) 对应的点:\(p_i^r = q_i, q_i^r = p_i\)

求出拓扑序,按拓扑序依次处理每个点:如果当前点 \(u\) 被打了标记,那么不选;否则选择 \(u\),并把 \(u^r\) 以及 \(u^r\) 出发能到达的所有点打上标记(递归进行,如果已经被打过标记就跳过,这样每个点只会被标记一次)。

这样对于任意的 \(i\)\(p_i\)\(q_i\) 不可能同时被选,已选的点也不与限制矛盾,只需要证明对于任意的 \(u\)\(u\)\(u^r\) 中至少有一个被选即可。

如果 \(u\) 第一次被标记的原因是 \(v\) 被选择, 那么 \(u\)\(v^r\) 出发能到达的点,由 2-SAT 的性质可得 \(v\)\(u^r\) 出发能到达的点,从而 \(v\) 在拓扑序上比 \(u^r\) 靠后。

假设存在一个 \(u\)\(u\)\(u^r\) 都被标记了,标记 \(u\) 的原因是 \(v_1\) 是被选择,标记 \(u^r\) 的原因是 \(v_2\) 被选择。那么 \(v_1\) 在拓扑序上比 \(u^r\) 靠后,\(v_2\) 在拓扑序上比 \(u\) 靠后。不妨设 \(u\) 在拓扑序上比 \(u^r\) 靠后,那么 \(v_2\) 在拓扑序上比 \(u^r\) 靠后,在处理 \(v_2\) 之前就会先处理 \(u^r\),矛盾。

所以该算法会得到一组合法的方案。