Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.