Heuristics for the data arrangement problem on regular trees

The data arrangement problem on regular trees (DAPT) consists in assigning the vertices of a given graph G to the leaves of a d-regular tree T such that the sum of the pairwise distances of all pairs of leaves in T which correspond to edges of G is minimised. This problem is a special case of the generic graph embedding problem and is NP-hard for every fixed \(d\ge 2\). In this paper we propose construction and local search heuristics for the DAPT and introduce a lower bound for this problem. The analysis of the performance of the heuristics is based on two considerations: (a) the quality of the solutions produced by the heuristics as compared to the respective lower bound (b) for a special class of instances with known optimal solution we evaluate the gap between the optimal value of the objective function and the objective function value attained by the heuristic solution, respectively.

1. In fact we can show that the DAPT is polynomially solvable in the case that the guest graph is an extended star and \(d\) is suitably chosen as in this example. In this case the optimal arrangement has a particular structure and is in general not contiguous. This and other polynomially solvable special cases of the DAPT are discussed in another paper we are working in.

The research was funded by the Austrian Science Fund (FWF): P23829.

Authors and Affiliations

1. Institut für Optimierung und Diskrete Mathematik, TU Graz, Steyrergasse 30, 8010 , Graz, Austria

   Eranda Çela

2. Institut für Statistik und Operations Research, Universität Graz, Universitätsstraße 15, Bauteil E/III, 8010 , Graz, Austria

   Rostislav Staněk

Corresponding author

Correspondence to Rostislav Staněk.

Appendix

1.1 Proof of Proposition  1

We make use of Observation 1 in order to show that \(d_T(\phi (v_i),\phi (v_j))= d_T(\phi _f(v_i),\phi _f(v_j))\) for any edge \((v_i,v_j)\) of the guest graph \(G\). For \(v_i \in V\), \(i=1,2,\ldots , n\), let us denote by \(p(i)\), \(p_f(i)\) the indices of the leaves \(\phi (v_i)\), \(\phi _f(v_i)\) of \(T\) in the canonical order, respectively. We clearly have \(p(i),p_f(i) \in 1,2,\ldots , d^h\), for all \(i=1,2,\ldots ,n\). According to Observation 1 we get

and

Consider the index \(p\) of an arbitrary leaf \(b_p\) of \(T\) (in the canonical order) written as \(p= (u-1)d^{h-e}+ (s - 1) d^{h - (e + 1)} + t\) for some natural numbers \(1\le u\le d^{e}\), \(1\le s\le d\) and \(1\le t\le d^ {h-(e+1)}\). \(u\) represents the index of the unique vertex \(x\) at level \(e\) which is an ancestor of \(b_p\), \(s\) represents the index of the \(d\)-regular subtree \(T_1\) of height \(h-(e+1)\) hanging on \(x\) and \(t\) represents the index of \(b_p\) in \(T_1\) according to the canonical order of the leaves of \(T_1\) induced by the canonical order of the leaves of \(T\). Then the following equality holds

for any \(1\le u\le d^e\), any \(1\le s\le d\) and any \(1\le t\le d^{h-(e+1)}\). Notice that according to Definition 4 \(\phi (v_i)\ne \phi _f(v_i)\) holds, only if \(p(i)= \Delta (g)+(l - 1) d^{h - (e + 1)} + t_i\) or \(p(i)= \Delta (g)+(r - 1) d^{h - (e + 1)} + t_i\) with some \( 1\le t_i \le d^{h - (e + 1)}\). Moreover, the following two implications hold for \(t_i =1,2,\ldots , d^{h - (e + 1)}\):

Consider now an edge \((v_i,v_j)\) with \(\phi (v_i)\ne \phi _f(v_i)\) or \(\phi (v_j)\ne \phi _f(v_j)\), which is equivalent to \(p(i)\ne p_f(i)\) or \(p(j)\ne p_f(j)\). There are two cases: (I) \(p(i)\ne p_f(i)\) and \(p(j)\ne p_f(j)\), or (II) just one of the inequalities \(p(i)\ne p_f(i)\), \(p(j)\ne p_f(j)\) holds.

Case I. In this case one of the following subcases can happen:

• Case Ia. \(p(i)= \Delta (g)+(l - 1) d^{h - (e + 1)} + t_i\) and \(p(j)= \Delta (g)+(l - 1) d^{h - (e + 1)} + t_j\), or

• Case Ib. \(p(i)= \Delta (g)+(r - 1) d^{h - (e + 1)} + t_i\) and \(p(j)= \Delta (g)+(r - 1) d^{h - (e + 1)} + t_j\), or

• Case Ic. \(p(i)= \Delta (g)+(l - 1) d^{h - (e + 1)} + t_i\) and \(p(j)= \Delta (g)+(r - 1) d^{h - (e + 1)} + t_j\), or

• Case Id. \(p(i)= \Delta (g)+(r - 1) d^{h - (e + 1)} + t_i\) and \(p(j)= \Delta (g)+(l - 1) d^{h - (e + 1)} + t_j\).

In Case Ic and in Case Id we get \(d(\phi (i),\phi (j))=d(\phi _f(i),\phi _f(j))=2(h-e)\) by applying (21) and considering (22), (23). In Case Ia and in Case Ib we get

Case II. Assume w.l.o.g. that \(p(i)=(g-1)d^{h-e}+ (l - 1) d^{h - (e + 1)} + t_i\) and let \(p(j)=(u-1)d^{h-e}+ (s - 1) d^{h - (e + 1)} + t_j\), where \(g\ne u\) or \(s\not \in \{l,r\}\). Clearly \(p_f(i)=(g-1)d^{h-e}+ (r - 1) d^{h - (e + 1)} + t_i\) and \(p_f(j)=p(j)=(u-1)d^{h-e}+ (s - 1) d^{h - (e + 1)} + t_j\). If \(u=g\) and \(s\not \in \{l,r\}\), then (21) together with Observation 1 implies \(d_T(\phi (i)\phi (j))=d_T(\phi _f(i)\phi _f(j))=2(h-e)\).

Otherwise, if \(u\ne g\), then (21) implies \(\left\lfloor \frac{p(i)-1}{d^k}\right\rfloor = \left\lfloor \frac{p_f(i)-1}{d^k}\right\rfloor \) for all \(k\ge h-e\) and

which together with Observation 1 implies then

Thus \( d_T(\phi (i)\phi (j))=d_T(\phi _f(i)\phi _f(j))\) for any edge \((v_i,v_j)\in E\).

1.2 Tables of numerical results

See Tables 2, 3, 4.

1.3 List of acronyms

• OS = optimal solution (if known).

• DB = degree bound.

• NAM = normal arrangement. The vertices \(\{v_1,v_2,\ldots , v_n\}\) of the guest graph are mapped to the leaves of the \(d\)-regular tree in their canonical order, i.e. by \(\phi (v_i)= b_i\), for \(i=1,2,\ldots ,n\).

• RAM = random arrangement for \(k = 1000\). \(k\) random mappings of the vertices of the guest graph into the leaves of the \(d\)-regular tree are constructed, their objective function values are computed, and the random mapping with the best objective function value is selected.

• RCAM = random contiguous arrangement for \(k = 1000\). \(k\) random contiguous mappings of the vertices of the guest graph into the leaves of the \(d\)-regular tree are constructed, their objective function values are computed, and the random mapping with the best objective function value is selected.

• G2 = arrangement produced by the leaf-driven greedy heuristic, see Sect. 4.1.

• BFSG = arrangement produced by the breadth-first search based greedy heuristics which tries each vertex as the starting vertex, see Sect. 4.1. If the graph has more then one connected components, they are arranged in a random order.

• TFSG = arrangement produced by the depth-first search based greedy heuristics which tries each vertex as the starting vertex, see Sect. 4.1. If the graph has more then one connected components, they are arranged in a random order.

• CHLS = arrangement produced by the construction heuristic which uses the local search approach to solve the MCBSSP, see Sect. 4.2.

• PEHVNA = arrangement produced by the pair-exchange heuristic for vertices which starts with the normal arrangement, see Sect. 4.3.1.

• SFHWI = arrangement produced by the shift-flip heuristic which accepts non-improving shifts, see Sect. 4.3.2. The algorithm terminates if no improvement is reached after \(3\) days of running time.

• – = the solution could not be found in a reasonable amount of time.

Reprints and permissions