论文标题
彩虹基地
Rainbow bases in matroids
论文作者
论文摘要
最近，Bérczi和Schwarcz证明了将矩阵分配到彩虹底座相对于其地面集合的给定分区的问题在算法上是可悲的。另一方面，许多特殊情况被打开。 我们首先表明，如果Matroid是图形的，问题仍然很难，回答了Bérczi和Schwarcz的问题。作为另一个特殊情况，我们考虑了确定是否可以将给定的挖掘物分解为跨越树木的子图的问题，并尊重每个顶点的indegree上的上限。我们证明这个问题也很困难。这回答了弗兰克的问题。 在文章的第二部分中，我们处理了覆盖彩虹底座的矩形的地面集的放松问题。除其他结果外，我们还表明，有一个线性函数$ f $，因此，如果每个分区中的每个分区类别都包含在大多数2个元素中，则可以将每种可以分解为$ k $ bases中的$ k $ bases。
Recently, it was proved by Bérczi and Schwarcz that the problem of factorizing a matroid into rainbow bases with respect to a given partition of its ground set is algorithmically intractable. On the other hand, many special cases were left open. We first show that the problem remains hard if the matroid is graphic, answering a question of Bérczi and Schwarcz. As another special case, we consider the problem of deciding whether a given digraph can be factorized into subgraphs which are spanning trees in the underlying sense and respect upper bounds on the indegree of every vertex. We prove that this problem is also hard. This answers a question of Frank. In the second part of the article, we deal with the relaxed problem of covering the ground set of a matroid by rainbow bases. Among other results, we show that there is a linear function $f$ such that every matroid that can be factorized into $k$ bases for some $k \geq 3$ can be covered by $f(k)$ rainbow bases if every partition class contains at most 2 elements.
