Algorithms and structural matroid theory

算法和结构拟阵理论

• 批准号: RGPIN-2016-03886
• 负责人: Geelen, Jim
• 金额: $ 3.93万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=690433
• 关键词: Algorithms; 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. ****** **

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