三维匹配问题是NP完全的

【三维匹配问题】
给定三个不相交的集合X、Y、Z,三个集合的大小都为n。给定一个三元组集合T \subseteq X \times Y \times Z,集合T的大小为m。
问:T中是否存在一个大小为n的子集T’,这个子集恰好包含X,Y,Z每个元素一次。
三维匹配问题其实是集合覆盖和集合包装问题的特例。

三维匹配问题是NP完全的
首先,很容易证明三维匹配问题是NP问题。只需要判断集合T’的大小是否为n,且包含X,Y,Z中每个元素一次。证明三维匹配问题是NPC的,可以通过3-SAT\leq_p三维匹配证明。
【3-SAT\leq_p三维匹配证明】
考虑任意的一个3-SAT实例,有n个变量x_1,x_2,…,x_n和k个子句C_1,C_2,…,C_n。构造3DM实例X,Y,Z,T。
对于每一个变量,都有一个零件相对应。如图9所示。每个零件有Core(核心)元素、Tip(边梢)元素、Triple元组。每一个零件大大小为2k。k为子句的大小。\
则,对于每一个变量x_i,建立:
A_i={a_{i,1},a_{i,2},…,a_{i,2k}}
B_i={b_{i,1},b_{i,2},…,b_{i,2k}}
t_{i,j}={(a_{i,j},a_{i,j+1},b_{i,j}}
构造的零件如图9所示。
在这里插入图片描述
图9 三维匹配的零件
对于每一个子句C_t加入两个元素P_t,P_t’,如果C_{t}包含x_{j},则加入三元组P=(P_t,P_t’,b_{j,2t}),显然一个C_i有三个三元组。
如果包含\overline x_j,则加入P=(P_t,P_t’,b_{j,2t-1});所以每个子句的三元组所包含的tip元组是不冲突的。即C_iC_j的三元组中没有相同的b元素。如图10所示。
在这里插入图片描述
图10 从3-SAT到三维匹配的归约,第一部分
定义,如果t_{ij}中的j为偶数,则称t_{ij}为偶三元组,如果j为奇数,则t_{ij}为奇三元组。
如果b_{i,j}中的j为偶数,则称b_{i,j}为偶tip,如果j为奇数,则称b_{i,j}为奇tip。
可以看到,要想core元素都被包含,且不被重复包含,则必须要么选择全部的偶三元组,要么选择全部的奇三元组。定义如果选择了全部的偶三元组,则x_{i}=0,否则,x_i=1
因此,可以看到,如果一个子句为1,则必然有一项的值为1,即选择该变量的所有奇三元组或所有偶三元组中。如果3-SAT是可满足的,则每个C_t的3个三元组中,至少有一个能够被选择。
对于每个没有被选择的tip元素,添加cleanup零件:Q={q_i,q_i’}。即有(n-1)k个tip等待覆盖。并且添加三元组(b_{i,j},q_i,q_i’)
如图11完成了3-SAT到三维匹配的归约。
在这里插入图片描述
图11 从3-SAT到三维匹配的归约,第二部分
此时,我们令:
X={a_{i,j}(j是偶数)} \vee{p_j} \vee {q_j} 。
Y={a_{i,j}(j是奇数)} \vee{p_j’} \vee {q_j’} 。
Z={b_{i,j}} 。
T={所有构造出来的三元组}。
可以看到,X,Y,Z三个集合的大小是相等的。
【对于每一个3-SAT实例】
假设有一个真值赋值,则如果x_i=1,则选择x_i对应的变量零件的所有奇三元组。若果c_j包含x_i,则c_j为1,则选择(p_j,p_j’,b_{t,2j}),因为b_{t,2j}为偶tip,因此没有被覆盖。如果x_i=0,则选择x_i对应的变量零件的所有偶三元组。若果c_j包含\overline x_i,则c_j为1,则选择(p_j,p_j’,b_{t,2j-1}),因为b_{t,2j-1}为奇tip,因此没有被覆盖。剩余没有被选中的tip元组被cleanup零件覆盖。
因此最终所有的元素都只被覆盖一次。
因此一个完美的三维匹配为:
T={变量中选择的三元组}\vee{子句中选择的三元组}\vee{cleanup中的三元组}
【对于一个三维匹配实例】
如果有一个完美三维匹配,则每个子句零件中的3个元组必须有一个被选择,则c_j为1。如果被选择的子句三元组中有偶tip,则说明该项的值为1,否则,该项的值为0。即存在一个可满足的真值赋值。此时,已经完成了3-SAT到三维匹配的证明。因此,三维匹配问题是一个NPC问题。

0

Leave a Reply

Your email address will not be published.