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

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.