The problem of covering the ground set of two matroids by a minimum number of common independent sets is notoriously hard even in very restricted settings, i.e.\ when the goal is to decide if two common independent sets suffice or not. Nevertheless, as the problem generalizes several long-standing open questions, identifying tractable cases is of particular interest. Strongly base orderable matroids form a class for which a basis-exchange condition that is much stronger than the standard axiom is met. As a result, several problems that are open for arbitrary matroids can be solved for this class. In particular, Davies and McDiarmid showed that if both matroids are strongly base orderable, then the covering number of their intersection coincides with the maximum of their covering numbers. Motivated by their result, we propose relaxations of strongly base orderability in two directions. First we weaken the basis-exchange condition, which leads to the definition of a new, complete class of matroids with distinguished algorithmic properties. Second, we introduce the notion of covering the circuits of a matroid by a graph, and consider the cases when the graph is ought to be 2-regular or a path. We give an extensive list of results explaining how the proposed relaxations compare to existing conjectures and theorems on coverings by common independent sets.
翻译：以最低数量通用独立机组来覆盖两架机器人地面的问题,即使在非常受限制的情况下,也是众所周知的难以解决的问题。 也就是说,当目标是要决定两个共同独立机组是否足够时, 也就是当目标是要决定两个共同独立机组是否足够时。 然而, 问题一般地概括了几个长期的开放问题, 找出了特别感兴趣的可移植案例。 强烈的有条理的机组组成了一个类别, 基础交换条件比标准正数要强得多。 因此, 可以为这一类任意的机组解决若干问题。 特别是, Davies 和 McDiarmid 表明, 如果这两种机组都非常基本有条理, 那么它们的交叉点数与其覆盖数字的最大值相吻合。 受这些问题的结果驱使, 我们建议从两个方向上放松强基调。 首先, 我们削弱基础交换条件, 从而导致定义一个新的、 完整的具有不同算法特性的机组。 其次, 我们提出用图表来覆盖一个机器人的电路圈的概念, 并且考虑这些案例, 当我们用图表来解释一个常规的路径, 或者一个普通的路径来解释。
相关内容
微信扫码咨询专知VIP会员