带特殊约束的无向图3着色对应布尔公式ϕ构造咨询

变量定义 #

我们首先定义布尔变量集合：

• 对任意顶点v ∈ V，任意颜色c ∈ {0,1,2}，x_{v,c}为真当且仅当顶点v被染为颜色c

已有的基础约束 #

首先梳理你已经明确的两类基础约束：

1. 每个顶点必须选且仅选一种颜色：
   • 至少选一种：对所有v ∈ V，加入约束 x_{v,0} ∨ x_{v,1} ∨ x_{v,2}
   • 最多选一种：对所有v ∈ V，任意c1 ≠ c2 ∈ {0,1,2}，加入约束 ¬x_{v,c1} ∨ ¬x_{v,c2}

核心特殊约束构造 #

你需要补充的是针对每条边的附加规则约束：对任意(u,v) ∈ E，若u和v颜色不同，则存在公共邻居w染第三种颜色。
我们可以把这条规则拆解为6种互斥的颜色组合情况，分别构造等价的合取范式约束：
对任意边(u,v) ∈ E，设N(u)∩N(v)为u和v的公共邻居集合，依次加入以下6条约束：

• 当u染0、v染1时，必须存在公共邻居染2：¬(x_{u,0} ∧ x_{v,1}) ∨ (∨_{w ∈ N(u)∩N(v)} x_{w,2})
• 当u染1、v染0时，必须存在公共邻居染2：¬(x_{u,1} ∧ x_{v,0}) ∨ (∨_{w ∈ N(u)∩N(v)} x_{w,2})
• 当u染0、v染2时，必须存在公共邻居染1：¬(x_{u,0} ∧ x_{v,2}) ∨ (∨_{w ∈ N(u)∩N(v)} x_{w,1})
• 当u染2、v染0时，必须存在公共邻居染1：¬(x_{u,2} ∧ x_{v,0}) ∨ (∨_{w ∈ N(u)∩N(v)} x_{w,1})
• 当u染1、v染2时，必须存在公共邻居染0：¬(x_{u,1} ∧ x_{v,2}) ∨ (∨_{w ∈ N(u)∩N(v)} x_{w,0})
• 当u染2、v染1时，必须存在公共邻居染0：¬(x_{u,2} ∧ x_{v,1}) ∨ (∨_{w ∈ N(u)∩N(v)} x_{w,0})

正确性与复杂度说明 #

• 正确性：上述约束等价于要求所有异色边都满足题设的公共邻居条件，若两个端点没有公共邻居，则对应约束会强制两个端点必须同色，完全符合题设规则。
• 多项式规模：总约束数量为O(n + m)，单条约束最长为O(n)，整体公式长度为O(nm)，属于多项式规模，满足可多项式计算的要求。

内容的提问来源于stack exchange，提问作者Andy