知识卡片

普通读书笔记卡 · 3716.a

补图把团转换为顶点覆盖

理解等级:高级

在图G中,k个顶点两两相邻当且仅当其补集在补图Ḡ中覆盖每条边。

因此把CLIQUE实例(G,k)变成VERTEX-COVER实例(Ḡ,|V|−k),可在多项式时间内构造,并保持是非答案。

这张卡片看不懂?

已有反馈 · 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 .