Algorithms and structural matroid theory

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

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. ****** **