# Search for isomorphic subgraphs

## 1 Formulation of the problem

Let $G$ and $H$ be given graphs. Search for isomorphic subgraphs consists in finding out whether the graph $G$ contains a subgraph isomorphic to $H$. If the answer is positive, then it is required to produce at least one such subgraph.

## 2 Properties of the problem

The search for isomorphic subgraphs is an NP-complete problem. Consequently, none of the known algorithms solves this problem in polynomial time.

## 3 Algorithms for solving the problem

Ullman's algorithm[1][2] solves the problem of isomorphic subgraphs in exponential time; moreover,

• for a fixed graph $H$, the time is polynomial;
• for a planar graph $G$, the computation time is linear (if the graph $H$ is fixed).

Алгоритм VF2[3] is specially designed for working with large graphs.

## 4 References

1. Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.
2. Ullmann, Julian R. “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism.” Journal of Experimental Algorithmics 15 (March 2010): 1.1. doi:10.1145/1671970.1921702.
3. Cordella, L P, P Foggia, C Sansone, and M Vento. “A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.” IEEE Transactions on Pattern Analysis and Machine Intelligence 26, no. 10 (October 2004): 1367–72. doi:10.1109/TPAMI.2004.75.