When Subgraph Isomorphism is Really Hard, and Why This Matters for Graph Databases
When Subgraph Isomorphism is Really Hard, and Why This Matters for Graph Databases
复制标题
DOI：
10.1613/jair.5768
复制
发表时间：
2018-01-01
影响因子：
5
通讯作者：
Trimble, James
中科院分区：
文献类型：
--
作者：
McCreesh, Ciaran;Prosser, Patrick;Trimble, James
子图同构问题涉及到决定模式图的副本是否出现在更大的目标图中。非诱导版本允许目标中的额外边缘，而诱导版本不允许。虽然这两种变体都是NP完全的，但受约束编程启发的算法可以在许多具有数千个顶点的现实问题实例上轻松运行。但是，它们不能处理这种大小的任意实例。我们将展示如何生成“真的很难”的子图同构问题，这是具有挑战性的计算与几百个顶点的目标，只有20个模式顶点的随机实例。对于非诱导版本的问题，这些情况下躺在一个可满足/不可满足的相变，其位置，我们可以预测;诱导的变体，更丰富的行为被观察到，和constrainedness提供了一个更好的措施比接近相变的难度。这些结果有实际的后果：我们解释了为什么广泛研究的“过滤/验证”索引技术在图形数据库中使用的是建立在一个误解的NP完全问题的经验硬度，并不能与任何合理的子图同构算法配对时是有益的。
The subgraph isomorphism problem involves deciding whether a copy of a pattern graph occurs inside a larger target graph. The non-induced version allows extra edges in the target, whilst the induced version does not. Although both variants are NP-complete, algorithms inspired by constraint programming can operate comfortably on many real-world problem instances with thousands of vertices. However, they cannot handle arbitrary instances of this size. We show how to generate "really hard" random instances for subgraph isomorphism problems, which are computationally challenging with a couple of hundred vertices in the target, and only twenty pattern vertices. For the non-induced version of the problem, these instances lie on a satisfiable / unsatisfiable phase transition, whose location we can predict; for the induced variant, much richer behaviour is observed, and constrainedness gives a better measure of difficulty than does proximity to a phase transition. These results have practical consequences: we explain why the widely researched "filter / verify" indexing technique used in graph databases is founded upon a misunderstanding of the empirical hardness of NP-complete problems, and cannot be beneficial when paired with any reasonable subgraph isomorphism algorithm.