做一做课后题吧~

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