子图的同构sat

Question

子图同构（SI）问题是一个计算任务，其中两个图G和H作为输入给出，并且必须确定G是否包含H. <<g。/p>

这是 np-complete问题。

我想知道它与SAT问题的关系。
特别是，我希望可以在整个SAT求解器（如Minisat）中解决此问题的实例。我需要一个可以在多项式时间内从SI到SAT问题的Alorithm，然后可以使用SAT分配来从节点找到映射g到h的节点。

任何想法？？？

Answer 1

a在SAT 2013论文中描述了图同构的SAT编码问题，"关于图形非同构的分辨率复杂性"。

Minisat是最著名的SAT解决器之一，但它的继任者可能更快且成功率更高。尝试CryptomInisat（版本2.9.5似乎比版本3更快；它支持并行线程），RISS3G或扣子。