团多项式归约到顶点覆盖

深度讲解团多项式归约到顶点覆盖核心结论可在多项式时间把任意团问题实例转化为顶点覆盖实例原图存在 k - 团 ⇔ 原图的补图存在∣V∣−k|V|-k∣V∣−k大小的顶点覆盖由此证明顶点覆盖是 NP 完全问题。一、CLIQUE≤PVertex Cover\boldsymbol{CLIQUE \le_P Vertex\ Cover}CLIQUE≤P​VertexCover团CLIQUE问题可以多项式时间 Karp 归约到顶点覆盖Vertex Cover问题符号≤P\boldsymbol{\le_P}≤P​释义沿用 NP 归约定义多项式算法输入一组团问题⟨G,k⟩\langle G,k \rangle⟨G,k⟩输出一组顶点覆盖问题⟨Gˉ,k′⟩\langle \bar G, k \rangle⟨Gˉ,k′⟩原问题GGG有kkk阶团⟺ \iff⟺构造后的Gˉ\bar GGˉ存在k′kk′大小的顶点覆盖推论若顶点覆盖能多项式求解则团问题也能多项式求解。二、Vertex Cover顶点覆盖问题定义 概念顶点覆盖问题输入给定无向图G(V,E)G(V,E)G(V,E)VVV顶点集EEE边集、正整数kkk输出是否能选出顶点子集S⊆VS\subseteq VS⊆V满足∣S∣k|S|k∣S∣k图中任意一条边的两个端点里至少有一个顶点落在集合SSS中通俗理解集合SSS叫做k - 顶点覆盖SSS里的顶点 “覆盖住所有边”每条边至少一头被选中。例图顶点1,4{1,4}1,4就是一个合法顶点覆盖所有边(1-2、1-3、1-4、1-6、4-3、4-5)(1\text{-}2、1\text{-}3、1\text{-}4、1\text{-}6、4\text{-}3、4\text{-}5)(1-2、1-3、1-4、1-6、4-3、4-5)都包含 1 或 4。补充判定类问题给定候选集合SSS逐条遍历边即可验证是否是点覆盖因此Vertex Cover ∈ NP。三、归约构造CLIQUE → Vertex Cover 定理与双向证明定理CLIQUE≤PVertexCover\boldsymbol{CLIQUE \le_P Vertex Cover}CLIQUE≤P​VertexCover归约构造规则灵魂补图变换给定任意团问题实例原图G(V,E)G(V,E)G(V,E)、目标团规模kkk构造补图Gˉ(V,Eˉ)\boldsymbol{\bar G(V,\bar E)}Gˉ(V,Eˉ)顶点集合和原图完全一致边取反原图GGG两点之间没有边⇒ 补图Gˉ\bar GGˉ两点连边原图GGG两点之间有边⇒ 补图Gˉ\bar GGˉ两点无边构造顶点覆盖参数k′∣V∣−kk |V|-kk′∣V∣−k总顶点数量减去团目标值kkk。核心等价命题G中存在大小为k的团 ⟺ Gˉ中存在大小为k′∣V∣−k的顶点覆盖\boldsymbol{G中存在大小为k的团 \iff \bar G中存在大小为k|V|-k的顶点覆盖}G中存在大小为k的团⟺Gˉ中存在大小为k′∣V∣−k的顶点覆盖方向 1正向推导⇒\boldsymbol{\Rightarrow}⇒GGG有kkk阶团⇒Gˉ\Rightarrow \bar G⇒Gˉ存在k′kk′顶点覆盖已知V′⊆VV\subseteq VV′⊆V是GGG里大小为kkk的团求证SV−V′SV-VSV−V′是Gˉ\bar GGˉ的顶点覆盖∣S∣∣V∣−kk′|S||V|-kk∣S∣∣V∣−kk′V′VV′是GGG的团V′VV′内部任意两个顶点在原图GGG中必有边相连任取补图Gˉ\bar GGˉ里任意一条边(u,v)∈Eˉ(u,v)\in \bar E(u,v)∈Eˉ由补图定义(u,v)∉E(u,v)\notin E(u,v)∈/E原图GGG没有这条边反证若u,vu,vu,v全都属于V′VV′因为V′VV′是团u,vu,vu,v在GGG一定有边和(u,v)∉E(u,v)\notin E(u,v)∈/E矛盾⇒u、v\Rightarrow u、v⇒u、v至少一个不在V′VV′也就是至少一个在SV−V′SV-VSV−V′根据顶点覆盖定义Gˉ\bar GGˉ每条边至少一个端点在SSS因此SSS是Gˉ\bar GGˉ的顶点覆盖∣S∣∣V∣−k|S||V|-k∣S∣∣V∣−k。通俗团的补集 补图的顶点覆盖。方向 2反向推导⇐\boldsymbol{\Leftarrow}⇐Gˉ\bar GGˉ有k′kk′顶点覆盖⇒G\Rightarrow G⇒G存在kkk阶团已知V′⊆VV\subseteq VV′⊆V是Gˉ\bar GGˉ的顶点覆盖∣V′∣∣V∣−k|V||V|-k∣V′∣∣V∣−k求证SV−V′SV-VSV−V′是GGG中大小为kkk的团∣S∣∣V∣−∣V′∣k|S||V|-|V|k∣S∣∣V∣−∣V′∣k只需证明SSS中任意两点在原图GGG中必有边任取SSS中两点u、vu、vu、v反证若u、vu、vu、v在原图GGG没有边则根据补图定义(u,v)∈Eˉ(u,v)\in \bar E(u,v)∈Eˉ补图里存在这条边V′VV′是Gˉ\bar GGˉ的顶点覆盖边(u,v)(u,v)(u,v)至少一个端点在V′VV′但u、v∈SV−V′u、v\in SV-Vu、v∈SV−V′都不在V′VV′出现矛盾⇒u、v\Rightarrow u、v⇒u、v在原图GGG一定有边SSS内所有点两两互连因此SSS是GGG的kkk阶团。通俗补图顶点覆盖的补集 原图的团。四、复杂度与 NP 完全结论多项式归约构造补图仅需要遍历全部顶点对时间复杂度O(∣V∣2)O(|V|^2)O(∣V∣2)属于多项式运算满足≤P\le_P≤P​归约要求NP 完全推导CLIQUE 是 NP 完全问题且CLIQUE≤PVertex Cover\text{CLIQUE}\le_P \text{Vertex Cover}CLIQUE≤P​Vertex CoverVertex Cover 本身属于 NP⇒顶点覆盖VertexCover是NP完全问题\boldsymbol{\Rightarrow 顶点覆盖Vertex Cover是NP完全问题}⇒顶点覆盖VertexCover是NP完全问题。五、核心对偶巧思总结团 ↔ 顶点覆盖在补图下对偶原图的团 → 它的补集是补图的点覆盖补图的点覆盖 → 它的补集是原图的团这个变换是 NP 归约经典构造承接3SAT≤PCLIQUE3SAT\le_P CLIQUE3SAT≤P​CLIQUE形成链条3SAT≤PCLIQUE≤PVertexCover\boldsymbol{3SAT\le_P CLIQUE \le_P Vertex Cover}3SAT≤P​CLIQUE≤P​VertexCover3SAT、团、顶点覆盖三者全是 NP 完全问题计算难度等价。