1
$\begingroup$

Given a (directed) n-tree $T=(N,E,r)$ rooted in $r\in N$, I want to represent each node $n\in N$ at most as a $m$-dimensional vector $v_n\in \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,b\in N. \|v_a-b_b\|_2\leq 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 E\cup \{(b,a)|(a,b)\in E\}. \|v_a-v_b\|_2\leq 1$
  • $\|v_1-v_4\|_2\leq 2$ by transitive closure
  • $\forall (a,b)\in V^2\backslash (E\cup \{(b,a)|(a,b)\in E\}. 3\leq \|v_a-v_b\|_2\leq 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?

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Thanks. I'll edit my question. What if m=hb, so to meet the omega requirement? $\endgroup$ – jackb Jun 5 at 16:24

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.