Algorithms and structural matroid theory

点击翻译按钮获取中文摘要

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.