hitch_hiker42's blog

Is it true for two trees, if their centroid trees are isomorphic, then the trees themselves are isomorphic too?
By hitch_hiker42, history, 4 years ago, In English

For context, I was solving this problem: https://cses.fi/problemset/task/1701, and was wondering if we can decompose the two trees into their respective centroid trees, and then compare their Euler tour sequence for bijection.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Not necessarily, as for given a tree there could be two possible centroids so there are multiple possible centroid trees for a single tree. However, you're on the right track. Instead of actually creating the centroid tree, just root both trees at the centroids. If there are two in each tree, try both possibilities. Then, just check the trees for bijection. For more info, see this comment.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can we check bijection using prufer code of the trees after rooting them onto their respective centroids?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      AFAIK, no it's not possible as the Prüfer Code of a tree is generated using the labels on the nodes. You can see a description of a linear time algorithm to detect rooted tree isomorphism on page 2 here.

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 8   Vote: I like it +3 Vote: I do not like it

    Thank you for the response, I read the paper in the given link and at first, struggled to understand it as it felt a little verbose but managed to do so after going through it about $$$2-3$$$ times. The algorithm was so elegant and smooth but felt a little ugly-ish while implementing as we needed to compare vectors lexicographically.

    Though, after implementing the AHU algorithm word-to-word, I realized that we might incorporate the structure of a subtree into a hash, and recursively compute the hash for a node from its children's hashes as follows:

    1. Sort the hashes of the children by value
    2. Run a polynomial hash, similar to one that we do for strings, over the children hashes by choosing a large prime as the multiplier, and another for the modulus.
    3. Though this is already a good hash function, it's still prone to rare collisions but we can improve the probability of no collisions by incorporating one random variable into the hash function and iterating the process $$$5-10$$$ times by changing the value of the random variable each time.

    The implementation gets easier significantly, compared to the naive adaptation of the AHU.

    Here are the two implementations for reference (both for the rooted version):

    1. The naive AHU implementation
    2. Hashing-based implementation
    → Reply