GRAPH PACKING OVER A ROOTED TREE.

This paper investigates the computational complexity of the graph packing problem over a rooted tree (GPT) as a generalization of the one-dimensional bin packing problem, where both the bins and the set of items to be packed are rooted trees. GPT is defined for two problem formulations, edge GPT (EPT) and node GPT (NPT). In EPT, the items packed in a bin cannot share any edge but can share some node, while in NPT the items can share neither node nor edge. It is proven that these problems are in general NP-complete, which strongly suggests that these problems are computationally intractable. However, for the case where the number k of different kinds of items is fixed the authors derive a recursive dynamic programming formula for the minimum number of bins required to pack all the items. This formula can be solved in polynomial time, if the bins and items are all uniform trees and/or comb-shaped trees in which each nonleaf parent node has the same number of sons.