  Dynamic programming is a powerful technique that is, unfortunately, often
inherently sequential. That is, there exists no unified method to parallelize
algorithms that use dynamic programming. In this paper, we attempt to address
this issue in the Massively Parallel Computations (MPC) model which is a
popular abstraction of MapReduce-like paradigms. Our main result is an
algorithmic framework to adapt a large family of dynamic programs defined over
trees.
  We introduce two classes of graph problems that admit dynamic programming
solutions on trees. We refer to them as "(polylog)-expressible" and
"linear-expressible" problems. We show that both classes can be parallelized in
$O(\log n)$ rounds using a sublinear number of machines and a sublinear memory
per machine. To achieve this result, we introduce a series of techniques that
can be plugged together. To illustrate the generality of our framework, we
implement in $O(\log n)$ rounds of MPC, the dynamic programming solution of
graph problems such as minimum bisection, $k$-spanning tree, maximum
independent set, longest path, etc., when the input graph is a tree.
