0%

NP-Complete问题乱证

做一做课后题吧~

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$所在的集合的变量全设为真,其余全设为假。

abab