TransWikia.com

Embedding a n-tree into a b-dimensional space

Theoretical Computer Science Asked by jackb on October 30, 2021

Given a (directed) n-tree $T=(N,E,r)$ rooted in $rin N$, I want to represent each node $nin N$ at most as a $m$-dimensional vector $v_nin mathbb{R}^m$ (From the current Yuri’s reply, m cannot be $b$). In particular, given $h$ the height of the tree (that is, the maximum path length starting from $r$), I want to guarantee that $forall a,bin N. |v_a-b_b|_2leq h$ if and only if there exists a directed path $pi(a,b)$ or $pi(b,a)$ in $T$.

Example, given the following tree rooted in $1$, $({1,2,3,4},;{(1,2), (1,3),(3,4)},1)$, I would instantiate the distance constraints as follows:

  • $forall (a,b)in Ecup {(b,a)|(a,b)in E}. |v_a-v_b|_2leq 1$
  • $|v_1-v_4|_2leq 2$ by transitive closure
  • $forall (a,b)in V^2backslash (Ecup {(b,a)|(a,b)in E}. 3leq |v_a-v_b|_2leq 4$

I was thinking to reduce this problem into the Distance Geometry Problem, and to use the former distances to feed known solvers like DGSOL or MD-Jeep: while the first commits non-negligible errors, MD-Jeep returns some errors during the computation of the torsion angle, and therefore cannot provide a viable solution. Is this a problem of the Distance Geometry Problem itself, or are there other implementations that would not suffer from the same problem? Alternatively, is it possible to express this problem using mathematical programming, i.e. using one of the already existing libraries?

2 Answers

For a directed tree, it is possible to find an embeeding in a n-dimensional space, where n is the maximum branching factor of the tree. This approach could be also generalized for (rooted) DAGs.

More to come in the forthcoming paper: https://www.researchgate.net/publication/342902961_Hierarchical_Embedding_for_DAG_Reachability_Queries

Answered by jackb on October 30, 2021

This is not possible if the dimension $m$ is fixed. Consider a complete $b$-ary tree, in which all edges are oriented from the root $r$. Then all vertices lie in a ball of radius $h$ around $v_r$. On the other hand, the distance between every two leaves is greater than $h$. Since there are $N = b^h$ leaves, we get that

there are $N$ points in a ball of radius $h$ such that all the pairwise distances between the points are greater than $h$

We must have that $m = Omega(log N) = Omega(h log b)$.

Answered by Yury on October 30, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP