Algorithms and structure in graphs and matroids

图和拟阵中的算法和结构

• 批准号: RGPIN-2015-04061
• 负责人: Guenin, Bertrand
• 金额: $ 3.13万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=612752
• 关键词: Algorithms; structure; graphs; matroids

This research proposal falls into the context of optimization, combinatorics, and theoretical computer science. We will investigate common generalizations to flows and graphs colouring. We will study the structure of certain minor closed classes of graphs and binary matroids with the aim of finding efficient recognition algorithms. The following is a summary of the projects in the proposal. Problem A. A quintessential minimax relation is the Max-Flow Min-Cut theorem that states that the largest amount of flow that can be sent between a pair of vertices in a graph is equal to the capacity of the smallest bottleneck separating these vertices. Furthermore, there exist efficient algorithms to find a maximum flow. We are interested in generalizing these results to multi-commodity flows and to flows in binary matroids. Two tantalizing conjectures by Seymour on the existence of fractional and integer flows are motivating our work. Problem B. Wagner proved that graphs without K5 minors can be constructed by pasting planar graphs and one special graph along edges and triangles. A graph G contains K5 as an odd-minor if K5 can be obtained from G by first deleting a subset of the edges and then contracting all the edges on a single cut. We wish to understand the structure of graphs that do not contain K5 as an odd minor. These graphs play a pivotal role in the study of multi-flows in graphs. These graphs can be 4-coloured, a generalization of the 4-color theorem, and feature in several important conjectures on colouring and homomorphisms. Problem C. Geelen, Gerards, and Whittle proved that any minor closed class of binary matroids can be characterized by a finite set S of excluded minors. Unfortunately, these results only indicate that the set S is finite and provide little guidance on how to obtain it. In an excluded minor characterization we look for an explicit description of S. Finding such characterizations has been a very fruitful area of research in both matroid and graph theory. Our goal is to find excluded minor characterizations and recognition algorithms for both even-cycle and even-cut matroids. The problems that are outlined in this proposal are widely viewed as important and resolving those would have profound implications. On the other hand some of these conjectures have been open for nearly four decades and are very challenging. We are however, in an enviable position now, as we have developed over the past few years, machinery that should greatly facilitate our projects. Indeed, we are very optimistic that we will be able to settle some long-standing conjectures during the period of this research proposal.

这项研究计划属于最优化、组合学和理论计算机科学的范畴。我们将研究对流和图着色的常见推广。我们将研究图和二元拟阵的某些次闭类的结构，目的是寻找有效的识别算法。以下是提案中的项目摘要。 问题A：典型的极大极小关系是最大流最小割集定理，它指出图中两个顶点之间可以传输的最大流量等于分隔这些顶点的最小瓶颈的容量。此外，还存在寻找最大流的有效算法。我们感兴趣的是将这些结果推广到多商品流和二元拟阵中的流。Seymour关于分数流和整数流存在的两个诱人的猜想激励着我们的工作。 问题B.Wagner证明了不含K5子式的图可以通过沿边和三角形粘贴平面图和一个特殊图来构造。图G包含K5作为奇子图，如果K5可以通过首先删除边子集然后收缩一次割上的所有边而从图G中获得。我们希望了解不包含K5作为奇子式的图的结构。这些图在图中多流的研究中起着举足轻重的作用。这些图可以是4-色的，这是4-色定理的推广，并且是关于着色和同态的几个重要猜想的特征。 问题C.Geelen，Gerards和Witter证明了二元拟阵的任何次闭类都可以由排除未成年人的有限集S来刻画。遗憾的是，这些结果只表明S集是有限的，并且对如何获得它几乎没有提供指导。在排除的次要刻画中，我们寻找S的显式刻画。找到这样的刻画在拟阵和图论中都是一个非常富有成果的研究领域。我们的目标是找到偶圈拟阵和偶割拟阵的排除次要刻画和识别算法。 这项提案中概述的问题被广泛认为是重要的，解决这些问题将具有深远的影响。另一方面，这些猜测中的一些已经公开了近40年，非常具有挑战性。然而，正如我们在过去几年所发展的那样，我们现在处于令人羡慕的地位，这些机器应该会极大地促进我们的项目。事实上，我们非常乐观地认为，在这项研究建议期间，我们将能够解决一些长期存在的猜测。