做一做课后题吧~
NP-Complete问题乱证
最长通路问题(longest path)
实例
图$G=<V,E>$,是否存在一条长度至少为$K$的路
证明
令$K = |V|$于是问题变成了Hamilton 通路问题,证毕。
集合包装问题
实例
令某个集合$|S| < \infty$, $C \subset 2^{S}$,$n = |C|$,询问是否存在$C$中的$k$个元素,使得任意两个互不交叉
证明
这个问题显然是团问题…
哈密尔顿子图划分(partition into Hamilton subgraph)
实例
图$G$,能否被划分成$k$个互补相交的集合使得每个导出子图包含一个哈密尔顿回路
证明
令$k=1$问题变成Hamilton 回路问题
最大公共子图问题(largest common subgraph)
实例
给两张图$G_{1}$,$G_{2}$,求两个最大的子图同构
证明
令第二张图为大小为$k$的完全图,整个问题变成了团问题。
最小平方和问题(minimum sum of squares)
实例
有限集合$A$ ,每个元素$a \in A$,每个元素均有一个值$f: A \rightarrow R$
将集合$A$分成$K$个互补相交的集合,使得每个子集的平方和的和小于等于$J$
证明
对于这个划分问题,考虑用二划分问题向这个方向来检测
考虑平方增长的速度比线性快得多,直接复制n份,然后规约二划分
这里不是很严谨,下次一定
返回顶点集(feedback vertex set)
实例
有向图$G=<V,A>$,正整数$K \leq |V|$
询问是否存在$V’\subset V$,$|V’|\leq K$,且$G$的每一条有向回路至少包含$V’$的一个点
证明
这很显然是个击中集问题。
四元素集合的严格覆盖(exact cover by 4-sets)
实例
即X3C问题直接扩展成4的形式
证明
考虑将X3C问题归约到X4C问题
对于每个X3C中的第$i$个集合$(a,b,c)$ ,直接扩展成$(a,b,c,d_{i})$
这样会多出$n$个分量,为了保证多出的$n$个分量,直接添加$C_{n}^{4}$个元素,来保证全部被覆盖
当然这样还是有问题的,即不一定能整除,直接补全就好了
支配集问题(dominating set)
实例
无向图$G=<V,E>$,$K \leq |V|, K\in N^{+}$
询问是否存在$V’\subset V$,st$|V’|\leq K$,且$\forall v\in V/V’,st,\exists u\in V’,uv\in E$
证明
被我xjb画画出来了。
这个东西显然和点覆盖问题很像。
于是考虑用点覆盖问题规约到这个问题。
假设一个点覆盖的实例是$G’=<V’,E’>$
构造一个新的图$G’’=<V’’,E’’>$
其中对于$E’$中的每条边$uv$,增量构造一个新的点$d_{i}$,增量构造两条边$ud_{i},vd_{i}$
这个问题就变成了一个支配集问题。
来一张图看看。
基础点覆盖问题
新构造3个点4,5,6,转化成一个支配集的问题
图3染色问题(graph 3-colorability)
实例
世人皆知
证明
爆智力*1
首先这个问题看起来就很3SAT,于是尝试从3SAT规约到这个问题。首先比较好想的一个部分就是
假设分别染成1,2,3这3种颜色,那么可以构造一个$K_{3}$,来指示真假。
然后就很困难了/youl
我在找了一发资料之后发现了下面这总构造方式,可以产生PQ的或$P\bigcup Q$
于是就很简单了…
至于怎么想出来的我还是不知道,我似乎对图论知识并不很敏感的样子…
划分为长度为2的通路(partition into paths of length 2)
实例
图$G=<V,E>$,$|V|=3q$
询问是否存在一个$V$的划分,使得每个互补相交的子集$V_{i}={v_{1},v_{2},v_{3}}$
其点导出子图,存在一条长度为2的路。
证明
考虑通过X3C问题规约到这个问题
假设有一个X3C的问题实例$(a_{i},b_{i},c_{i})$
构造$3q$个点,然后连边$(a_{i},b_{i}),(b_{i},c_{i})$
这样每次一个划分,就代表了选择了X3C问题中的一个元素。
k-median
实例
世人皆知
证明
考虑通过支配集问题归约到这个问题。
对于支配集问题的图$G=<V,E>$
将$V$中顶点复制一份作为工厂,每个点向自己和关联点连$d=0$的边。
然后就做完了/youl
Steiner tree
实例
世人皆知
证明
被爆智力*3,被爆到不想写证明了
http://profs.sci.univr.it/~rrizzi/classes/Complexity/provette/Santuari/steiner.pdf
集合分裂问题(set splitting)
实例
一个有限集$S$,$C \subset 2^{S}$
询问是否存在一个$S$的划分$S_{1},S_{2}$,使得$\forall x \in C, x \not\subset S_{1},x\not\subset S_{2}$
证明
被爆智力*2
这个东西真的好靠直觉呀/youl,给个提示就好想了。
考虑使用3SAT归约到这个问题,下面来着手构造$C$
对于$(a_{i},b_{i},c_{i})$来说,构造$(a_{i},\overline a_{i}),(b_{i},\overline b_{i}),(c_{i},\overline c_{i})$
以及$(d, \overline a_{i}, \overline b_{i}, \overline c_{i})$
假设这个集合分裂问题得到了一个解,将$d$所在的集合的变量全设为真,其余全设为假。