M-convexity of the minimum-cost packings of arborescences

Abstract

The aim of this paper is to reveal the discrete convexity of the minimum-cost packings of arborescences and branchings. We first prove that the minimum-cost packings of disjoint $k$ branchings (minimum-cost $k$-branchings) induce an ${\mathrm{M}}^{♮}$-convex function defined on the integer vectors on the vertex set. The proof is based on a theorem on packing disjoint $k$-branchings, which extends Edmonds' disjoint branchings theorem and is of independent interest. We then show the $\mathrm{M}$-convexity of the minimum-cost $k$-arborescences, which provides a short proof for a theorem of Bernáth and Király (SODA 2016) stating that the root vectors of the minimum-cost $k$-arborescences form a base polyhedron of a submodular function. Finally, building upon the ${\mathrm{M}}^{♮}$-convexity of $k$-branchings, we present a new problem of minimum-cost root location of a $k$-branching, and show that it can be solved in polynomial time if the opening cost function is ${\mathrm{M}}^{♮}$-convex.

It has been found that the proof is incomplete