For What Families of Subgraphs, the Subgraph Isomorphism Problem Can be Solved in Polynomial Time?

37 Views Asked by At

Are there families of subgraphs that are arbitrarily large and are still easy to match in a larger graph ? By a "family" I mean a graph sequence $\mathcal{G}=\{G_1,G_2,\ldots,G_n,\ldots\}$ which is generated by a polynomial time algorithm and the total size of the graphs increase monotonically $|V_n|+|E_n|\ge|V_{n-1}|+|E_{n-1}|$ (this can be relaxed in many ways). Other than trivial cases like paths and cycles, I suspect there are other sequences (hopefully with automorphism groups of various size).