NP-hard问题求解

对NP-hard问题，有几种处理方法：

• 为问题实例添加限制，相当于利用问题中的特殊结构简化问题
• 寻找精确算法
• 寻找近似算法

实例研究：

最大独立集(稳定集)问题：假设无向图G=(V(G),E(G))是无环的，求最大独立集 $I\subseteq V(G)$

若对于任意线性序列(linear ordering)，贪心算法都能找到最大独立集，则称此图是拟阵的(matroidal)

完美消除序列(Perfect Elimination Ordering)是一个 $V(G)$ 中的一个序列 $x_1,\cdots,x_n$ ，使得 $\forall 1\leq i\leq n$ ， $x_i$ 是 $G[\{x_i,\cdots,x_n\}]$ 中的简单点(simplicial vertex)。其中 $G[X]=(X,E(G)\cap X\times X)$ 是G的导出子图。

推论：任意区间图都有一个完美消除序列

定理：可以在多项式时间内得到区间图的一个区间表示，从这个区间表示可以得到一个完美消除序列

恰当染色(proper coloring)对应一个将顶点分为独立集的划分

色数(chromatic number)是最小的恰当染色的颜色数

定理：给定图G的一个完美消除序列，贪心染色算法使用的颜色数等于最大团的大小

分裂图(split graph)是可以划分成一个团和一个独立集的图

弦图(chordal graph)是没有一个长度大于4的环作为导出子图的图(顶点数大于3的环至少有一个弦)，弦图都是完美图

推论：每个分裂图都有完美消除序列。分裂图既是弦图，又是弦图的补图

定理：G有一个完美消除序列，当且仅当它是一个弦图

$S\subseteq V(G)$ 是一个分离子(separator)如果 $G[V(G)\setminus S]$ 有比G更多的连通分量

S是最小分离子，如果S是分离子且对任意 $x\in S$ ， $S\setminus x$ 不是分离子

引理：任意最小分离子都是一个团

图G的三角剖分是通过给G添加边得到的弦图

图的树宽(tree-width) $treewidth(G)=\{\omega(H)-1: H是G的最小三角剖分\}$ ，其中 $\omega(H)$ 是H的最大团的大小

最大团图(graph of maximal cliques)的顶点是最大团，相交的团之间有边且权重为交集大小

团树定理(clique tree theorem)：弦图的最小生成树是一个宽度为 $\omega(G)-1$ 的树分解(tree decomposition)

图G收缩(contracting)一个边xy后得到图 $G'=(V',E')$ ，$V'=V(G)\setminus \{x,y\}\cup \{z\}$ （z是新顶点）， $E'=E(G[V\setminus\{x,y\}])\cup \{zt: t\in N_G(x)\cup N_G(y)\}$ ($N_G(x)$ 是x的邻居顶点集)

H是G的一个子式(minor)如果H可以通过图G删除顶点，删除边或收缩边得到，子式的树宽小于等于原图的树宽

如果 $treewidth(G)=k$ 那么以G为主图(primal graph)的CSP问题可以在多项式时间内求解（使用k一致性算法）