我们将 ROMAN-SUBSET 定义为以下问题：
输入：有向图 G = ( V , E ) 和一个正整数 k
输出：如果存在 V 的子集 R 使得 | 右 | <= k ，并且使得 G 中的每个有向电路都包含至少一个来自 R 的顶点，则输出应为“TRUE”，否则应为“FALSE”。
假设顶点覆盖 (VC) 问题是 NP 完全的，我必须证明 ROMAN-SUBSET 也是 NP 完全的。据我了解，这意味着获取 VC 输入，对其进行修改，然后显示将其插入 ROMAN-SUBSET 算法将产生 VC 问题的结果。
我很难进行转型。我知道VC的输入是一个图G和一个整数k，问题是是否存在一个覆盖G中每条边的V的子集R，使得|R| <= k。很明显，从 ROM 到 VC，R 和 k 是相似的，但我的困难是确定如何转换图形，以便每个有向循环（对于 ROM）中的 1 个顶点对应于每条边（对于 VC）。如何修改图表以证明 VC 可以简化为 ROM？
谢谢！
这里是建筑。
G = (V, E)以VC中的无向图为例。现在定义有向图，G1 = (V, E1)其中对于其中的每条边(u,v)都有E两条边(u,v)和(v,u)。E1
换句话说，新图与旧图相同，但每条无向边都被两条有向边替换，形成一个 2 循环。
声称是从 ROM 开始G1跟随 VC 在G.
事实上，假设 ROM on 的答案G1是 FALSE。然后对于一组小于k顶点的每个选择，都存在一个不在该集合中的循环。所以存在一个端点不在集合中的边。但这意味着对于小于k顶点集合的相同选择，G存在一条端点不在集合中的边，因此 VC 的答案是 FALSE。
相反，假设 ROM on 的答案G1是 TRUE。然后存在一个V包含少于k顶点的子集，因此给定任何循环，循环中至少存在一个顶点，该顶点在集合中。但这意味着对于E集合中它的一个端点中的任何边缘，因为边缘 inE对应于 2 循环E1。因此，VC 的答案是正确的。