Algorithms and structural matroid theory

罗伯逊和西摩的《图形次要项目》是一系列23篇论文，它们改变了图论领域，并对理论计算机科学产生了重大影响；这种影响的程度被超过6500条引文所见证。拟阵理论为涉及图和矩阵的问题提供了一个统一的框架，并在组合优化、编码理论、信息论和计算生物学等不同领域中得到了应用。这项建议中的研究特别适用于编码理论，因为线性码实际上与可表示拟阵相同，并且由于未成年人对码给出了一种自然的包容关系。*自1999年以来，我与Bert Gerards(荷兰的Centrum Voor Wiskunde en Informatica)和Geoff Whitter(新西兰惠灵顿维多利亚大学)合作，将Neil Robertson和Paul Seymour的图形次要项目扩展到拟阵。我们的Matroid未成年人项目取得了巨大的成功，大多数主要目标都已经实现。这项建议解决了一些基本的算法问题。*我们的主要目标是：*(1)简化Matroid Minor 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. ****** **