3
$\begingroup$

Let $T$ be a tree with $V$ and edges $E$. Let a linear arrangement $\pi$ of $T$ be a bijective mapping from nodes to integers in the range $\{1, \dots, |V|\}$. You can think of $\pi$ as defining the position of each node in an arrangement on a line.

Now define the length of an edge $E = \{u,v\}$ in $T$ under $\pi$ to be the absolute value of the difference in positions for $u$ and $v$ according to the linear arrangement $\pi$: \begin{equation} l_\pi(u,v) = |\pi(u) - \pi(v)|. \end{equation}

Linear arrangements of this kind are studied in, for example, the Optimal Linear Arrangement problem (Chung, 1984), where the goal is to find a $\pi$ for a fixed $T$ which minimizes $\sum_{\{u,v\} \in E} l_\pi(u,v)$.

My problem is: given a tree $T$ and a linear arrangement $\pi$, generate new linear arrangement $\pi^\prime$ randomly at uniform from the set of possible linear arrangements of $T$ while preserving the same distribution over edge lengths as in the original $\pi$.

An example tree with linear arrangement $\pi$ is shown below. Each edge is marked with its length. The distribution of edge lengths in this tree under this particular linear arrangement is $(1, 1, 1, 2, 2)$ (3 of length 1 and 2 of length 2).

Example tree

Now here is the same tree under a different linear arrangement $\pi^\prime$, which has the same distribution of edge lengths $(1,1,1,2,2)$.

Example tree 2

I am looking for an efficient algorithm to generate random linear arrangements that preserve the distribution over edge lengths. Here is a baseline rejection-sampling algorithm:

  1. Starting with tree $T$ with $n$ nodes and linear arrangement $\pi$, calculate the list of edge lengths for $T$ under $\pi$. Call this $L$.
  2. Generate a random linear arrangement $\pi^\prime$ by drawing from the set of $n!$ linear arrangements of $T$.
  3. Calculate the list of edge lengths for $T$ under $\pi^\prime$. Call this $L^\prime$. If $L^\prime = L$, accept the sample. If $L^\prime \neq L$, reject the sample and go to step 2.

I’m looking for an algorithm to draw a random sample from the linear arrangements that match $L$ which is faster than rejection sampling. No need to enumerate the whole set (although that would be nice too).

This question is related to, but distinct from, my earlier question: Generate random labeled tree with constrained edge lengths. In that question, I was looking for random trees. In this question, I am looking for random linear arrangements of a fixed tree, while preserving the topology of the tree.

$\endgroup$
4
  • 1
    $\begingroup$ What do you actually want? Since there may be n! many legal permutations, the algorithm cannot enumerate all in less time. Is it faster "delay" that you are after? Are you familiar with bandwidth? $\endgroup$ – Pål GD Mar 14 '20 at 10:16
  • $\begingroup$ I’m looking for a random sample, not an enumeration. Also, there are many fewer than n! linear arrangements that match the desired edge lengths. $\endgroup$ – Richard Futrell Mar 15 '20 at 15:43
  • $\begingroup$ Thanks for pointing out the bandwidth problem. In the language of my post, the bandwidth problem is asking if there exists a linear arrangement of a tree $T$ such that max(L) $\le b$. In my case, I already have a linear arrangement satisfying $L$ so I know at least one exists, and I’m looking for a uniform random sample of another one. $\endgroup$ – Richard Futrell Mar 15 '20 at 16:49
  • 1
    $\begingroup$ For many problems where finding one solution is hard, it's also hard to solve the variant where we are given one solution and asked whether a second solution exists. I suggest seeing if you can adapt the proof techniques shown there to show that this applies to your situation as well. $\endgroup$ – D.W. Mar 15 '20 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.