M-convexity of the minimum-cost packings of arborescences
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2018
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916659665567744 |
|---|---|
| author | Takazawa, Kenjiro |
| author_facet | Takazawa, Kenjiro |
| contents | 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}^\natural$-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}^\natural$-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}^\natural$-convex. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1805_08381 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | M-convexity of the minimum-cost packings of arborescences Takazawa, Kenjiro Combinatorics Discrete Mathematics 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}^\natural$-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}^\natural$-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}^\natural$-convex. |
| title | M-convexity of the minimum-cost packings of arborescences |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/1805.08381 |