子图组合搜索算法

Question

有了这个无向图

在这张图中，我有以下类型的不同节点 [A、B、C、D、E]。这意味着可能存在具有相同类型的不同节点

现在假设您有一组节点类型 [A,B,E]。您不知道图中给定的节点是哪个节点，您唯一知道的是每个节点的类型。

您要做的是找到最适合给定节点集的节点。节点必须相互连接

我一直在测试一个包含以下步骤的算法:

1. 将图转换为链表

2. 考虑那些给定的类型以及节点类型出现的次数，生成所有节点之间的所有可能组合。给定的示例是 [A,B,E]，但它可以是其他集合，例如 [A,B,C,A]。[A,B,E] 的一些可能(并非全部)组合是:

3. 检查这些组合中的节点是否相互连接

4. 最适合的是所有节点都连接的第一个组合。

问题是给定图中的节点数。对于小节点集和小图，算法是可以的。但是当节点数量增加时，我有数千种可能的组合，这些组合会消耗大量内存。

我一直在寻找能够以低成本内存有效解决此问题的算法。

我花了几天时间阅读和测试各种算法，直到现在我找不到更好的解决方案。

非常感谢您的建议

Answer 1

这称为 Graph Motif 问题，不幸的是它是 NP-hard，即使该图是最大度数为 3 的树:参见 https://people.mpi-inf.mpg.de/~hermelin/Conference%20Publications/Connected%20Motifs.pdf 中的定理 1

这意味着不太可能存在可以解决此问题的任何多项式时间算法。