Complexity of packing common bases in matroids
Complexity of packing common bases in matroids
复制标题
在拟阵中包装公共碱基的复杂性
DOI：
--
复制
发表时间：
2019
影响因子：
2.7
通讯作者：
Tamás Schwarcz
中科院分区：
文献类型：
--
作者：
Kristóf Bérczi;Tamás Schwarcz
拟阵优化中一个最有趣的未解决问题是两个拟阵的k个不相交公共基的存在性的表征。这个问题的重要性可以通过一长串可以表述为特殊情况的猜想来很好地说明，比如伍德尔关于有向图中不相交的聚结的猜想，或者罗塔关于碱基重排的美丽猜想。本文证明了该问题在秩表模型下是困难的，即，我们证明了不存在用多项式个数的独立查询来决定两个拟阵的公共基集是否可以划分为k个公共基的算法。即使在$$k=2$$ k = 2的特殊情况下，我们的复杂度结果也成立。通过一系列的约简，我们还证明了在两个拟阵中填充公共基的抽象问题包括有向图中的NAE-SAT问题和完全偶因子问题。这些结果表明，该问题不仅在独立oracle模型中困难，而且还包括np完全的特殊情况，当$$k=2$$ k = 2时，其中一个矩阵是划分矩阵，而另一个矩阵是线性的，并由显式表示。
One of the most intriguing unsolved questions of matroid optimization is the characterization of the existence of k 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, such as Woodall’s conjecture on packing disjoint dijoins in a directed graph, or Rota’s beautiful conjecture on rearrangements of bases. In the present paper we prove that the problem is difficult under the rank oracle model, i.e., we show that there is no algorithm which decides if the common ground set of two matroids can be partitioned into k common bases by using a polynomial number of independence queries. Our complexity result holds even for the very special case when $$k=2$$ k = 2 . Through a series of reductions, we also show that the abstract problem of packing common bases in two matroids includes the NAE-SAT problem and the Perfect Even Factor problem in directed graphs. These results in turn imply that the problem is not only difficult in the independence oracle model but also includes NP-complete special cases already when $$k=2$$ k = 2 , one of the matroids is a partition matroid, while the other matroid is linear and is given by an explicit representation.