Recognizing small subgraphs

Although the general problem of subgraph isomorphism is NP‐complete, polynomial‐time algorithms exist for recognizing any fixed subgraph. However, certain subgraphs appear easier to recognize than others. In this paper, we present general algorithms for fixed‐subgraph isomorphism which improve or unify previous results. In particular, we present an O(n^fm) algorithm for recognizing a fixed subgraph H with flower number f within a graph G with n vertices and m edges. Special cases of this algorithm match the best algorithms known for recognizing small paths, cycles, and cliques. Further, we improve previous results for recognizing C₅ and small even cycles C_2k, k ≥ 3.