3
$\begingroup$

The $d$-dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can be solved optimaly in polynomial time (Chung, [1984]).

So, what about trees in higher (fixed) dimension? To be more precise:

$d$-dimensional Arrangement Problem of Trees:

$\text{Input}: d$, a tree $T=(V,E),$ $|V|=n=a^d$

$\text{Task}$: Find a bijection $b: V\rightarrow\{{1,\ldots,\sqrt[d]{n}\}}^d$, such that

$$\sum_{e=(v,w)\in E}|b(v)-b(w)|_1$$ is minimized.

Can we generalize an algorithm from the linear case, or can we show that this problem is still $NP$-hard? Since both questions seem hard (to me), is there at least a constant factor approximation algorithm (down from $O(\log n)$ for general graphs) for this problem?

Ideas, thoughts or paper recommendations would be appreciated.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.