Polynomial-time algorithms for Subgraph Isomorphism in small graph classes of perfect graphs

In this paper, we present a polynomial-time algorithm for the case where the base graphs are chordal graphs and the pattern graphs are co-chain graphs. We also present a linear-time algorithm for the case where the base graphs are trivially perfect graphs and the pattern graphs are threshold graphs. These results answer some of the open questions of Kijima et al. (2012). To present a complexity contrast, we then show that even if the base graphs are somewhat restricted perfect graphs, the problem of finding a pattern graph that is a chain graph, a co-chain graph, or a threshold graph is NP-complete.