论文标题
关于包装彩虹的复杂性
On the complexity of packing rainbow spanning trees
论文作者
论文摘要
矩阵优化中最重要的问题之一是找到两个矩形的不相交的共同基础。该问题的重要性是由可以表达为特殊案例的一长串猜想来阐明的。 Bérczi和Schwarcz表明，这个问题通常很困难，因此确定可拖动和顽固的实例之间的边界是有意义的。 在本文中，我们研究了一种特殊情况，其中一个矩形是分区的矩形，而另一个是图形的矩阵。这种设置等同于包装彩虹跨越树木的问题，这是在有方向图中包装植曲线的问题的扩展，这是由埃德蒙兹（Edmonds）在Discoint Arborescences上的开创性结果回答的。我们通过证明NP算法是否包含两个不相交的彩虹跨越树是NP完整的，我们可以补充他的结果。即使对于非常特殊的情况，我们的复杂性结果也会成立，当图形是两个跨越树的结合，每个颜色类别都包含两个边缘。作为推论，我们对有关定向$ K $ - 分区连接的Digraphs的分解的问题给出了负面答案。
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érczi 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.
