归约算法 - 将任何 SGI 问题重新转换为子集和
是否可以将任何子图同构问题转换为子集和问题，以便可以使用可用于解决子集和问题的动态规划技术来解决SGI问题？
Is it possible to cast any subgraph isomorphism problem as a subset sum problem so that it is possible to use dynamic programming techniques available for solving the subset sum problem to solve the SGI problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是的，您可以做到这一点，但是每次已知的归约都会产生指数级大数的子集和问题。
（另外，btilly，你的作业检测器坏了。）
Yes, you could do it, but every reduction known would produce a subset-sum problem with exponentially large numbers.
(Also, btilly, your homework detector is broken.)
我不明白这是怎么做到的。子集和问题的权重与图的结构之间没有立即清晰的映射。两个问题之间的唯一关系是图的子集和子集和问题中集合的子集。用于子集和的伪多时间（动态编程）算法对一组数字和有界和进行操作 - 我严重怀疑是否有任何方法可以以这种格式对图的结构进行编码。但是，考虑到这是一个家庭作业问题，我可能是错的:)
I don't see how this could be done. There's no immediately clear mapping between the weights of the subset-sum problem and the structure of the graph. The only relation between the two problems would be the subset of the graph and the subset of the set in the subset-sum problem. The pseudo-polytime (dynamic programming) algorithm for subset-sum operates over a set of digits and a bounded sum - I seriously doubt there's any way to encode the structure of the graph in this format. But, given that this is a homework problem, I might be wrong :)