从顶点覆盖减少以证明 NP 完全
我们将 ROMAN-SUBSET 定义为以下问题：
输入：有向图 G = ( V , E ) 和正整数 k
输出：如果存在 V 的子集 R，使得 |右 | <= k ，并且 使得 G 中的每个有向电路至少包含一个顶点 来自 R ，那么输出应该是“TRUE”，否则，它应该是 “假”。
假设顶点覆盖（VC）问题是NP完全的，我必须证明ROMAN-SUBSET也是NP完全的。据我了解，这意味着获取 VC 输入，对其进行修改，然后表明将其插入 ROMAN-SUBSET 算法将产生 VC 问题的结果。
我在转变方面遇到了很大的困难。我知道 VC 输入是图 G 和整数 k，问题是是否存在 V 的子集 R 覆盖 G 中的每条边，使得 |R| <= k。很明显，从 ROM 到 VC，R 和 k 是相似的，但我的困难在于确定如何转换图，以便每个有向循环（对于 ROM）中的 1 个顶点对应于每条边（对于 VC）。我怎样才能修改图表来证明VC可以简化为ROM？
谢谢！
We define ROMAN-SUBSET as the following problem:
INPUT: Directed graph G = ( V , E ) and a positive integer k
OUTPUT: If there is a subset R of V such that | R | <= k , and
such that every directed circuit in G includes at least one vertex
from R , then the output should be "TRUE", otherwise, it should be
"FALSE".
Assuming that the Vertex Cover (VC) problem is NP-complete, I must prove that ROMAN-SUBSET is also NP-complete. From what I understand, that means taking the VC input, modifying it, and then showing that plugging it into the ROMAN-SUBSET algorithm will yield the result of the VC problem.
I'm having a really tough time coming up with the transformation. I know that the VC input is a graph G and an integer k, and the problem is whether or not there exists a subset R of V that covers every edge in G, such that |R| <= k. So clearly, the R and k are similar from ROM to VC, but my difficulty is identifying how to transform the graph so that 1 vertex in every directed cycle (for ROM) corresponds to every edge (for VC). How can I go about modifying the graph to prove that VC can be reduced to ROM?
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是施工。
以 VC 中的无向图 G = (V, E) 为例。
现在定义有向图
G1 = (V, E1)，其中E中的每条边(u,v)都有两条边<E1中的 code>(u,v) 和(v,u)。换句话说，新图与旧图相同，但每个无向边都被替换为形成 2 个循环的两个有向边。
据称，
G1上的 ROM 遵循G上的 VC。事实上，假设
G1上的 ROM 的答案是 FALSE。那么对于少于k个顶点的集合的每个选择，都存在不在该集合中的循环。因此存在一条边，其端点不在集合中。但这意味着，对于G中少于k个顶点的集合的相同选择，存在一条端点不在集合中的边，所以VC的答案是FALSE。相反，假设
G1上的 ROM 的答案为 TRUE。那么存在V的子集，其中包含少于k个顶点，因此给定任何循环，循环中至少存在一个顶点，该顶点位于集合中。但这意味着对于E中的任何边，其端点之一在集合中，因为E中的边对应于E1中的 2 个周期代码>.因此 VC 的答案是 TRUE。Here is the construction.
Take undirected graph
G = (V, E)as in VC.Now define the directed graph
G1 = (V, E1), where for every edge(u,v)inEthere are two edges(u,v)and(v,u)inE1.In other words the new graph is the same as the old one, but every undirected edge is replaced with two directed edges that form a 2-cycle.
The claim is that from ROM on
G1follows VC onG.Indeed, suppose that the answer for ROM on
G1is FALSE. Then for every choice of a set of less thankvertices there exists a cycle not in this set. So there exists an edge whose endpoints are not in the set. But this means that for the same choice of the set of less thankvertices inGthere exists an edge whose endpoints are not in the set, so VC's answer is FALSE.Conversely, suppose that the answer for ROM on
G1is TRUE. Then there exists a subset ofVcontaining less thankvertices, so that given any cycle there exists at least one vertex in the cycle, which is in the set. But this means that for any edge inEone of its endpoints in in the set, because an edge inEcorresponds to a 2-cycle inE1. Thus the answer for VC is TRUE.