In terms of Subgraph isomorphism I believe Directed Acyclic Graphs (DAG's) are in the np-complete complexity class.
What about Poly-trees (oriented trees)? These are DAG's where the possible paths from a node are all trees. Unlike trees, Poly-tree nodes can have several 'parents'.
Are polytrees in the same sub-graph isomorphism complexity class of DAG's or are there known polynomial-time algorithms for sub-polytree isomorphism?