My first  thought: if two polytrees are isomorphic then their underlying trees must be isomorphic: this surely cuts the problem space down immensely.  I suspect that the methods which show that the isomorphism problem for trees is in P can be modified to work for polytrees too: something along the lines of 

a) find the center(s) of the underlying trees

b) consider the subtrees meeting at the center: either there are few of them, in which case divide and conquer again, or there are many, in which case the trees in question are small.

I don't immediately see how to implement this, but the fact that trees are in P strongly suggests to me that polytrees should be too.

Of course, you could just wait a little while and see if Babai and others manage to tighten his proof  that GI is almost in P to get it actually in P!

Neil, thanks for the comprehensive and imaginative answer. I might consider this if I get to this question later (I am focused on something else now). Maybe the fact that all paths from such central node seem enumerable in P-Time through something like Breadth-first search could be a sign that your idea might work.

I am also very grateful for pointing me to Babai's remarkable result. I was not aware of it and it is important to my work.

Kind regards.

Fernando.

I think it is in P, by doing something like this (assume the polytrees have n nodes each):

1- Using any algorithm like DFS or BFS you can partition (some nodes will be in several trees) the polygraphs in components, each one being a tree rooted in a node with outdegree equal to 0 in the polytree(this can be done in O(n)).

2- Then you have two sets of trees, and you must check if they are isomorphic. This can be modelled as a bipartite matching problem. Each tree is represented as a node, and two nodes (belonging to different sets of trees) are connected iff the corresponding trees are isomorphic (this can be done in O(n) + n ^ 2 * the time needed by the isomorphism algorithm). Next use a maximum bipartite matching algorithm like Hopcroft-Karp to find a maximum bipartite matching of the constructed graph, if the matching is not perfect then there is no isomorphism.

4- Now, as the algorithms for the isomorphism of trees give you the isomorphims itself (i.e. the map between the set of nodes), we can try to reconstruct the original polytrees. Using the maps (from the isomorphisms) and the maximum bipartite matching found, you can check whether the nodes in several trees match, and that's all.

Reynaldo, congratulations and thank you for the elaborated answer, that I admit I had some difficulty in following, because I lack some concepts in graph theory. If I get back to this topic (I am focused on something else now) I will evaluate your answer more carefully. If it works, it means that some other new way I had in mind of doing this will no longer be particularly interesting, since Poly-tree isomorphism is already known to be in P.

Kind regards.

Fernando.