Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.13722 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- Subgraph isomorphism compares two graphs (sets of nodes joined by edges) to determine whether they contain a common subgraph. Many applications require identifying the subgraph, not just deciding its existence. A particularly common use case, using graphs with labeled nodes, seeks to find instances of a smaller pattern graph with $p$ nodes in the larger data graph with $d$ nodes. The problem is NP-complete, so that naïve solutions are exponential in $p + d$. A wide range of heuristics have been proposed, with the best complexity $O(p^2d^2)$. This paper outlines ASSIST (Approximate Swarming Subgraph Isomorphism through Stigmergy), inspired by the ant colony optimization approach to the traveling salesperson problem. ASSIST is linearithmic, $O(p \log d)$, and also supports matching problems (such as temporally ordered edges, inexact matches, and missing nodes or edges in the data graph) that frustrate other heuristics.