|タイトル||Polymatroid-Based Capacitated Packing of Branchings|
Edmonds (1973) characterized the condition for the existence of a packing of spanning arborescences and also that of spanning branchings in a directed graph and gave polynomial-time algorithms to find such packings if they exist. Durand de Gevigney, Nguyen and Szigeti (2013) generalized the first problem and solved the matroid-based arborescence packing problem. We consider the polymatroid-based arborescence packing problem, which is a generalization of the latter problem. We formulate two problem settings: the unsplittable version and the splittable version. We show that the unsplittable version is strongly NP-complete. Whereas, for the splittable version, which generalizes the capacitated version of the spanning arborescence packing problem, we show that this problem can be solved in strongly polynomial time. Actually, we provide a strongly polynomial-time algorithm for the problem of the polymatroid-based capacitated packing of branchings for this version. This is a joint work with Zoltán Szigeti.