×

Packing branchings under cardinality constraints on their root sets. (English) Zbl 1458.05090

Summary: Edmonds’ fundamental theorem on arborescences characterizes the existence of \(k\) pairwise arc-disjoint spanning arborescences with prescribed root sets in a digraph. In this paper, we study the problem of packing branchings in digraphs under cardinality constraints on their root sets by arborescence augmentation. Let \(D=(V+x,A)\) be a digraph, \(\mathcal{P}=\{I_1,\dots,I_l\}\) be a partition of \([k]\), \(c_1,\dots,c_l,c_1^\prime,\dots,c_l^\prime\) be nonnegative integers such that \(c_\alpha\leq c_\alpha^\prime\) for \(\alpha\in[l]\), \(F_1,\dots,F_k\) be \(k\) arc-disjoint \(x\)-arborescences in \(D\) such that \(\sum_{i\in I_\alpha} d_{F_i}^+(x)\leq c_\alpha^\prime\) for \(\alpha\in [l]\). We give a characterization on when \(F_1,\dots,F_k\) can be completed to arc-disjoint spanning \(x\)-arborescences \(F_1^\ast,\dots,F_k^\ast\) such that for any \(\alpha\in [l]\), \(c_\alpha\leq\sum_{i\in I_\alpha}d_{F_i^\ast}^+(x)\leq c_\alpha^\prime\).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bérczi, K.; Frank, A., Variations for Lovász’ submodular ideas, (Grötschel, M.; Katona, G. O.H., Building Bridges Between Mathematics and Computer Science. Building Bridges Between Mathematics and Computer Science, Bolyai Society Series: Mathematical Studies, vol. 19 (2008)), 137-164 · Zbl 1163.05017
[2] Bérczi, K.; Frank, A., Packing arborescences, (Iwata, S., RIMS Kokyuroku Bessatsu B23: Combinatorial Optimization and Discrete Algorithms (2010)), 1-31 · Zbl 1217.05057
[3] Bérczi, K.; Frank, A., Supermodularity in unweighted graph optimization I: Branchings and matchings, Math. Oper. Res., 43, 3, 726-753 (2018) · Zbl 1434.05120
[4] Bérczi, K.; Frank, A., Supermodularity in unweighted graph optimization II: Matroidal term rank augmentation, Math. Oper. Res., 43, 3, 754-762 (2018) · Zbl 1434.05121
[5] Bérczi, K.; Frank, A., Supermodularity in unweighted graph optimization III: Highly-connected digraphs, Math. Oper. Res., 43, 3, 763-780 (2018) · Zbl 1434.05082
[6] Bérczi, K.; Király, T.; Kobayashi, Y., Covering intersecting bi-set families under matroid constraints, SIAM J. Discrete Math., 30, 3, 1758-1774 (2016) · Zbl 1344.05112
[7] Cai, M.-C., Arc-disjoint arborescences of digraphs, J. Graph Theory, 7, 2, 235-240 (1983) · Zbl 0498.05033
[8] Catlin, P. A.; Grossman, J. W.; Hobbs, A. H.; Lai, H.-J., Fractional arboricity, strength and principal partitions in graphs and matroids, Discrete Math. Appl., 40, 285-302 (1992) · Zbl 0773.05033
[9] Chen, C. C.; Koh, K. M.; Peng, Y. H., On the higher-order edge toughness of a graph, Discrete Math., 111, 113-123 (1993) · Zbl 0789.05086
[10] Chen, Z.-H.; Lai, H.-J., The higher-order edge toughness of a graph and truncated uniformly dense matroids, J. Combin. Math. Combin. Comput., 22, 157-160 (1996) · Zbl 0863.05046
[11] Durand de Gevigney, O.; Nguyen, V.-H.; Szigeti, Z., Matroid-based packing of arborescences, SIAM J. Discrete Math., 27, 567-574 (2013) · Zbl 1268.05165
[12] Edmonds, J., Edge-disjoint branchings, Combinatorial algorithms, (Courant Comput. Sci. Sympos., Vol. 9. Courant Comput. Sci. Sympos., Vol. 9, New York Univ., New York, 1972 (1973), Algorithmics Press: Algorithmics Press New York), 91-96
[13] Fan, G.; Jiang, H.; Li, P.; West, D. B.; Yang, D.; Zhu, X., Extensions of matroid covering and packing, European J. Combin., 76, 117-122 (2019) · Zbl 1402.05032
[14] Fortier, Q.; Király, Cs.; Léonard, M.; Szigeti, Z.; Talon, A., Old and new results on packing arborescences in directed hypergraphs, Discrete Appl. Math., 242, 26-33 (2018) · Zbl 1384.05119
[15] Frank, A., On disjoint trees and arborescences, (Algebraic Methods in Graph Theory. Algebraic Methods in Graph Theory, Colloquia Mathematica Soc. J. Bolyai, vol. 25 (1978), North-Holland: North-Holland Amsterdam), 159-169
[16] Frank, A., Covering branching, Acta Sci. Math. (Szeged), 41, 77-81 (1979) · Zbl 0424.05033
[17] Frank, A.; Tardos, É., An application of submodular flows, Linear Algebra Appl., 114-115, 329-348 (1989) · Zbl 0672.05035
[18] Fujishige, S., A note on disjoint arborescences, Combinatorica, 30, 247-252 (2010) · Zbl 1224.05406
[19] Kamiyama, N., Arborescence problems in directed graphs: Theorems and algorithms, Interdiscip. Inform. Sci., 20, 1, 51-70 (2014) · Zbl 1288.05116
[20] Kamiyama, N.; Katoh, N.; Takizawa, A., Arc-disjoint in-trees in directed graphs, Combinatorica, 29, 197-214 (2009) · Zbl 1212.05209
[21] Király, Cs., On maximal independent arborescence packing, SIAM J. Discrete Math., 30, 4, 2107-2114 (2016) · Zbl 1350.05138
[22] Király, Cs.; Szigeti, Z.; Tanigawa, S., Packing of Arborescences with Matroid Constraints via Matroid IntersectionEGRES Technical Reports, TR-2018-08 (2018), Egerváry Research Group
[23] Leston-Rey, M.; Wakabayashi, Y., Packing in generalized kernel systems, Math. Program., 149, 209-251 (2015) · Zbl 1310.90099
[24] Lovász, L., A generalization of Konig’s theorem, Acta Math. Acad. Sci. Hungar., 21, 3-4, 443-446 (1970) · Zbl 0209.55202
[25] Lovász, L., On two minimax theorems in graph theory, J. Combin. Theory Ser. B, 21, 2, 96-103 (1976) · Zbl 0337.05115
[26] Matsuoka, T.; Tanigawa, S., On reachability mixed arborescence packing, Discrete Optim., 32, 1-10 (2019) · Zbl 1506.05176
[27] Nash-Williams, C. St. J.A., Decompositions of finite graphs into forests, J. Lond. Math. Soc., 39, 12 (1964) · Zbl 0119.38805
[28] Payan, C., Graphes equilibre et arboricité rationnelle, European J. Combin., 7, 263-270 (1986) · Zbl 0663.05051
[29] Schrijver, A., Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, Vol. 24 (2003), Springer: Springer Berlin
[30] Szegő, L., On covering intersecting set-systems by digraphs, Discrete Math., 234, 1-3, 187-189 (2001) · Zbl 0993.05116
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.