Подсчет подсписных экземпляров

Question

Предположим, у меня есть большой (несколько тысяч узлов) ориентированный граф G и гораздо меньший (3-5 узлов) направленный граф g. Я хочу подсчитать, сколько изоморфизмов g находятся в G. Другими словами, я хочу знать, сколько уникальных наборов узлов в G соответствует g. Я понимаю, что это экземпляр проблемы изоморфизма подграфа и поэтому NP-полно. Однако, учитывая, что вы можете предположить, что g невелик, существует ли какой-либо разумно эффективный алгоритм для этого?

Answer 1

Несмотря на то, что изоморфизм графа является NP-полным, проблемы, с которыми вы сталкиваетесь в реальном мире, часто довольно просты. Простой грубой силы должно быть достаточно: пусть M_i будет набором карт из первых i узлов g в узлы G. Начните с m_0, содержащего пустую карту и протягивая ее по одному узлу за раз, отбрасывая любые карты, которые нарушают ограничение x->y iff m(x)->m(y).

Вы хотите заказать узлы в g, чтобы очень много обрезки происходило раньше. Предполагая, что ваши графики довольно разрежены, вам понадобится заказ, который как можно раньше завершает как можно большее количество ребер, возможно, dfs из узла с наивысшей степенью точности.