8
$\begingroup$

Lets consider two node-labeled rooted trees Q and D. According to wikipedia definition ( https://en.wikipedia.org/wiki/Tree_homomorphism ) a mapping m from the nodes of Q to the nodes of D is a tree homomorphism iff :

  • m maps the root of Q to the root of D
  • if node c is a child node of p in Q then m(c) is a child of m(p) in D
  • and for every node n in Q, the label of n is the same as the label of m(n) in D.

What is the best algorithm in terms of time complexity to compute ALL such mappings from Q to D ?

I have heard that there exists one algorithm that computes all these mappings in O(|Q|.|D|) worse case time complexity but the best I could find on my own has worse case time complexity O(|Q|.(log |Q|).|D|).

The only algorithm with O(|Q|.|D|) time complexity related to tree homomorphism that I could find CHECKS if there exists such homomorphism from Q to D and computes all the IMAGES OF THE ROOT of Q ; but do not compute ALL the complete mappings (for all the nodes). You can get the article here (it is called MORPHISM p17-18) : http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.37.4645&rep=rep1&type=pdf

I have been searching among a lot of other articles :

  • those dealing with pure theoritical computer science (graph theory for example) usually do not adress this problem specifically and dont give a tight bound (some just stop at the polynomial time complexity claim).
  • those dealing with XML, XPath and XQuery are too much complicated (I dont understand them) or they go far beyond the strict computation of tree homomorphism (XPath and XQuery are indeed very rich languages).

I would appreciate some help on this topic either in terms of references to articles (not too complicated please) or in terms of a beautiful algorithm that does the job with a nice time complexity proof :-) (I know I'm dreaming...)

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.