0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

From the definition of planar graphs - that you can always draw them on plane in such a way that edges just meet on nodes - I believe all polytrees are planar graphs (please correct me if I am wrong).

Now since subgraph isomorphism of planar graphs has polinomial time algorithms available, I guess Sub-Polytrees isomorphism is also in the polynomial time complexity class.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.