On the complexity of packing rainbow spanning trees

DOI10.1016/J.DISC.2022.113297arXiv2206.11924MaRDI QIDQ6402998FDOQ6402998

Authors: Kristóf Bérczi, Gergely Csáji, Tamás Király 

Publication date: 23 June 2022

Abstract: One of the most important questions in matroid optimization is to find disjoint common bases of two matroids. The significance of the problem is well-illustrated by the long list of conjectures that can be formulated as special cases. B'erczi and Schwarcz showed that the problem is hard in general, therefore identifying the borderline between tractable and intractable instances is of interest. In the present paper, we study the special case when one of the matroids is a partition matroid while the other one is a graphic matroid. This setting is equivalent to the problem of packing rainbow spanning trees, an extension of the problem of packing arborescences in directed graphs which was answered by Edmonds' seminal result on disjoint arborescences. We complement his result by showing that it is NP-complete to decide whether an edge-colored graph contains two disjoint rainbow spanning trees. Our complexity result holds even for the very special case when the graph is the union of two spanning trees and each color class contains exactly two edges. As a corollary, we give a negative answer to a question on the decomposition of oriented $k$-partition-connected digraphs.

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

This page was built for publication: On the complexity of packing rainbow spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402998)