algorithm - 约简算法 - 将任何 SGI 问题重铸为子集和

Question

是否可以将任何子图同构问题转换为子集和问题，以便可以使用可用于解决子集和问题的动态规划技术来解决 SGI 问题？

score 1 · Accepted Answer

是的，你可以做到，但已知的每一次减少都会产生一个具有指数大数字的子集和问题。

（另外，顺便说一句，你的作业检测器坏了。）

score 0 · Accepted Answer

我不明白这是怎么做到的。子集和问题的权重与图的结构之间没有立即明确的映射。这两个问题之间的唯一关系是图的子集和子集和问题中集合的子集。子集和的伪多时间（动态编程）算法在一组数字和有界和上运行 - 我严重怀疑有任何方法可以以这种格式编码图的结构。但是，鉴于这是一个家庭作业问题，我可能错了:)

2 回答 2