Graph Packing over a Rooted Tree

Abstract

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 under two problem settings, 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. We first prove 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, we derive a recursive formula of dynamic programming 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 non-leaf node has the same number of sons. Furthermore, for GPT's with bins of uniform (d, H) trees and only one kind of item, of uniform (d, h) trees, we derive explicit formulas for the number of bins required.