知识卡片
补图把团转换为顶点覆盖
在图G中,k个顶点两两相邻当且仅当其补集在补图Ḡ中覆盖每条边。
因此把CLIQUE实例(G,k)变成VERTEX-COVER实例(Ḡ,|V|−k),可在多项式时间内构造,并保持是非答案。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
The reduction algorithm takes as input an instance 〈G, k〉 of the clique problem and computes the complement G in polynomial time. The output of the reduction algorithm is the instance 〈G, |V| − k〉 of the vertex-cover problem. To complete the proof, we show that this transformation is indeed a reduction: the graph G contains a clique of size k if and only if the graph G has a vertex cover of size |V| − k.
参考来源
- 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[90000,95000))。
- 结论依据:原文§34.4–34.5的3-CNF、团、顶点覆盖和哈密顿环归约;图已核对,跨单元证明留待续读。
- 原始内容:The reduction algorithm takes as input an instance 〈 G, k 〉 of the clique problem and computes the complement G in polynomial time. The output of the reduction algorithm is the instance 〈 G , | V | − k 〉 of the vertex-cover problem. To complete the proof, we show that this transformation is indeed a reduction: the graph G contains a clique of size k if and only if the graph G has a vertex cover of size | V | − k .