  We show that the problem of constructing tree-structured descriptions of data
layouts that are optimal with respect to space or other criteria from given
sequences of displacements, can be solved in polynomial time. The problem is
relevant for efficient compiler and library support for communication of
noncontiguous data, where tree-structured descriptions with low-degree nodes
and small index arrays are beneficial for the communication soft- and hardware.
An important example is the Message-Passing Interface (MPI) which has a
mechanism for describing arbitrary data layouts as trees using a set of
increasingly general constructors. Our algorithm shows that the so-called MPI
datatype reconstruction problem by trees with the full set of MPI constructors
can be solved optimally in polynomial time, refuting previous conjectures that
the problem is NP-hard. Our algorithm can handle further, natural constructors,
currently not found in MPI.
  Our algorithm is based on dynamic programming, and requires the solution of a
series of shortest path problems on an incrementally built, directed, acyclic
graph. The algorithm runs in $O(n^4)$ time steps and requires $O(n^2)$ space
for input displacement sequences of length $n$.

Data Structures and Algorithms