Проблема изоморфизма подграфов (SI) - это вычислительная задача, в которой два графа G и H заданы в качестве входных данных, и нужно определить, содержит ли G подграф, изоморфный H.
Это проблема NP-Complete.
Я хочу знать его связь с проблемой SAT.
В частности, я хочу, чтобы экземпляры этой проблемы могли быть решены с помощью SAT Solver (например, miniSAT). Мне нужен алгоритм, который может выполнять отображение от SI к задаче SAT за полиномиальное время, а затем назначение SAT может использоваться, чтобы найти отображение от узлов G к узлам H.
Любая идея ???
