On arborescence packing augmentation in hypergraphs
| Autor: | Hoppenot, Pierre, Szigeti, Zoltán |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We deepen the link between two classic areas of combinatorial optimization: augmentation and packing arborescences. We consider the following type of questions: What is the minimum number of arcs to be added to a digraph so that in the resulting digraph there exists some special kind of packing of arborescences? We answer this question for two problems: $h$-regular \textsf{M}-independent-rooted $(f,g)$-bounded $(\alpha, \beta)$-limited packing of mixed hyperarborescences and $h$-regular $(\ell, \ell')$-bordered $(\alpha, \beta)$-limited packing of $k$ hyperbranchings. We also solve the undirected counterpart of the latter, that is the augmentation problem for $h$-regular $(\ell, \ell')$-bordered $(\alpha, \beta)$-limited packing of $k$ rooted hyperforests. Our results provide a common generalization of a great number of previous results. Comment: 17 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|