Algorithms and structural matroid theory

由Robertson和Seymour发起的Graph Minors Project是一个由23篇论文组成的系列，这些论文改变了图论领域，并对理论计算机科学产生了重大影响;超过6500次引用证明了这种影响的程度。 拟阵理论为涉及图和矩阵的问题提供了一个统一的框架，并在不同的领域，如组合优化，编码理论，信息论和计算生物学中有应用。这个建议中的研究特别适用于编码理论，因为线性码实际上与可表示拟阵相同，并且因为子式给出了码的自然包含关系。自1999年以来，我一直与Bert Gerards（荷兰的Centrum voor Wiskunde en Informatica）和Geoff Whittle（新西兰惠灵顿的维多利亚大学）合作，将Neil Robertson和Paul Seymour的Graph Minors Project扩展到拟阵。 我们的未成年人项目取得了巨大的成功，大部分主要目标都已经实现。该提案解决了一些仍然存在的基本算法问题。我们的主要目标是：*（1）在Matroid Minors Project中验证算法。 三个计算方面的拟阵未成年人项目（即未成年人测试定理，建设性版本的拟阵未成年人结构定理，和三要素问题）目前纠缠成一个复杂的算法。 我们建议通过为三元问题找到一个单独的直接算法来解开这些部分;在这个问题中，我们给出了一个矩阵的三列，我们问矩阵中是否有一个“电路”包含所有三个给定的元素。(2)改进算法的分析。 小测试定理给出了一个有效的搜索一个特定的“小”在一个给定的拟阵。 该定理目前只表明存在一个有效的算法，但它并没有明确地给你一个可以编程到计算机中的算法。* （3）更好地理解框架拟阵。 框架拟阵是拟阵子结构理论中最重要的子闭拟阵类。 然而，在这个阶段，我们并不太了解这门课。我们建议通过开发一种识别框架拟阵的算法来解决这个问题。* (4)开发编码理论的应用程序。 二进制线性码在信息论中具有重要意义，码的距离度量了它的容错能力。 已知计算二进制线性码的距离的问题是“NP难”的，这意味着不太可能存在有效的算法。然而，我们希望开发有效的算法时，从任何固定的“小封闭”类的代码的代码选择。****** **

The Graph Minors Project, of Robertson and Seymour, is a sequence of 23 papers that have transformed the area of graph theory and have made a significant impact in theoretical computer science; the extent of that impact is witnessed by more than 6500 citations. Matroid theory provides a unifying framework for problems involving graphs and matrices, and has applications in diverse areas such as combinatorial optimization, coding theory, information theory, and computational biology. The research in this proposal is particularly applicable to coding theory, since linear codes are effectively the same as representable matroids and since minors give a natural containment relation on codes.*** Since 1999, I have worked with Bert Gerards (the Centrum voor Wiskunde en Informatica, the Netherlands) and Geoff Whittle (Victoria University of Wellington, New Zealand) on extending the Graph Minors Project of Neil Robertson and Paul Seymour to matroids. Our Matroid Minors Project has been a spectacular success with most of the major goals having been attained. This proposal addresses a number of fundamental algorithmic issues that remain.*** Our main goals are:***(1) Simplify the algorithms in the Matroid Minors Project. Three computational aspects of the Matroid Minors Project (namely the Minor-Testing Theorem, the constructive version of the Matroid Minors Structure Theorem, and the Three Elements Problem) are currently entangled into one complicated algorithm. We propose to disentangle the parts by finding a separate direct algorithm for the Three-Elements Problem; in this problem we are given three columns of a matrix and we ask whether or not there is a "circuit" in the matrix that contains all three of the given elements.***(2) Improve the analysis of the algorithms. The Minor-Testing Theorem gives an efficient that searches for a particular "minor" in a given matroid. The theorem currently only shows that there exists an efficient algorithm, but it does not explicity hand you an algorithm that could be programmed into a computer. ****(3) Develop a better understanding of frame matroids. "Frame matroids" arise in the Matroid Minors structure theory as the most important minor-closed class of matroids. However, at this stage we do not understand the class very well. We propose to address this by developing an algorithm for recognizing frame matroids.***(4) Develop applications in coding theory. Binary linear codes are of fundamental importance in information theory, and the distance of a code measures its tolerance to errors. The problem of computing the distance of a binary linear code is known to be "NP-hard", which means that it is unlikely that there exists an efficient algorithm. However, we hope to develop efficient algorithms when the code is chosen from any fixed "minor-closed" class of codes. ****** **