Algorithms and structure in graphs and matroids

图和拟阵中的算法和结构

• 批准号: RGPIN-2015-04061
• 负责人: Guenin, Bertrand
• 金额: $ 3.13万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=652601
• 关键词: 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.最大流最小割定理（Max-Flow Min-Cut Theorem）是一个典型的极大极小关系，它指出在图中的一对顶点之间可以发送的最大流量等于分隔这些顶点的最小瓶颈的容量。此外，还存在找到最大流量的有效算法。我们有兴趣将这些结果推广到多商品流和二进制拟阵流。西摩关于分数流和整数流存在性的两个诱人猜想激发了我们的工作。*问题B。瓦格纳证明了不含K5子式的图可以通过沿沿着边和三角形粘贴平面图和一个特殊图来构造。一个图G包含K5作为奇子式，如果K5可以通过首先删除G的一个边子集，然后在单个割上收缩所有边而从G获得。我们希望了解不包含K5作为奇子式的图的结构。这些图在图的多流研究中起着举足轻重的作用。这些图可以是4色的，这是4色定理的推广，并且在着色和同态的几个重要猜想中发挥了作用。*问题C Geelen、Gerards和Whittle证明了二元拟阵的任何次闭类都可以用有限的排除次集S来刻画。不幸的是，这些结果只表明，集S是有限的，并提供了如何获得它的指导很少。在一个排除的小特征，我们寻找一个明确的描述S。寻找这样的特征一直是拟阵和图论中一个非常富有成果的研究领域。我们的目标是找到偶圈和偶割拟阵的排除次要特征和识别算法。该提案中概述的问题被广泛认为是重要的，解决这些问题将产生深远的影响。另一方面，其中一些开放了近四十年，非常具有挑战性。然而，正如我们在过去几年中所发展的那样，我们现在处于一个令人羡慕的地位，这一机制应大大促进我们的项目。事实上，我们非常乐观地认为，我们将能够在本研究提案期间解决一些长期存在的问题。