Structural graph theory for colouring algorithms and network reliability

着色算法和网络可靠性的结构图理论

• 批准号: RGPIN-2022-03697
• 负责人: Cameron, Benjamin
• 金额: $ 1.18万
• 依托单位: The King's University (Edmonton)
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750495
• 关键词: Structural; graph; theory; colouring; algorithms

I intend to pursue research on the structure of graphs, the mathematical models for networks. My research interests can be divided into two main areas depending on whether the graph is modelling a dynamic network, where certain components may fail, or a static network. For static graphs, I am motivated by applications to scheduling, logistics, and optimizing resource allocation to develop efficient certifying algorithms to colour families of graphs. If a family of graphs contains only a finite number of (k+1)-critical graphs, then a polynomial-time algorithm to determine k-colourability can be implemented by searching for (k+1)-critical graphs as induced subgraphs of the input graph. If a (k+1)-critical graph is found, then it can be returned as a certificate to quickly verify the output. Therefore, to develop efficient certifying algorithms for colouring families of graphs, I will look at the structural characterizations of k-critical graphs in many families. My top priority is to prove a dichotomy theorem classifying for which graphs H there are only finitely many k-critical H-free graphs for all values of k. Recent work of Chudnovsky, Goedgebeur, Schaudt and Zhong together with my recent work with Hoàng and Sawada imply that the only remaining unknown case is when H=P4+nP1 for all positive integers n. In addition to this dichotomy, I plan to classify critical (G,H)-free graphs for various graphs G and H, especially for G=2P2. This is motivated by the fact that many families of graphs contain the same infinite family of 2P2-free graphs. Success in this area will either lead to new polynomial-time certifying algorithms, which will be useful toward a corresponding complexity dichotomy for colouring algorithms, or new highly structured infinite families of critical graphs. Techniques will include a hybrid of structural graph theory and exhaustive generation by computer search. A prominent model for a dynamic graph is where vertices (or edges) are functional independently at random with some probability p. Reliability is defined as the probability that the graph has some property of interest, such as properties related to connectedness, domination number, and cop number. Maximizing the reliability of a graph has applications to telecommunication, social networks, and cybersecurity. A graph is uniformly most reliable (UMR) if it has greatest reliability among all graphs in a given family. Classifying UMR graphs allows for the design of an optimal network, even as component failures change over time. I plan to continue to classify UMR graphs under a variety of reliability models using combinatorial and analytic techniques. Classical results on the analytic theory of polynomials (such as the theorems due to Gauss and Lucas, Rouché and Möbius) are expected to have elegant applications as they have in my previous work and in other work on reliability (such as in the work by Brown and Colbourn, Royle and Sokal and Wagner).

我打算继续研究图的结构，网络的数学模型。我的研究兴趣可以分为两个主要领域，这取决于图是建模动态网络，某些组件可能会失败，还是静态网络。对于静态图，我的动机是调度，物流和优化资源分配的应用程序，以开发有效的认证算法来着色图形的家庭。如果一个图族只包含有限个（k+1）-临界图，则通过搜索（k+1）-临界图作为输入图的导出子图，可以实现确定k-可染性的多项式时间算法。如果找到一个（k+1）-临界图，那么它可以作为证书返回，以快速验证输出。因此，为了开发有效的证明算法，着色的图形家庭，我会看看在许多家庭的k-临界图的结构特征。我的首要任务是证明一个二分法定理，分类哪些图H只有1000个k-临界H-自由图的所有值的k。最近的工作Chudnovsky，Goedgebeur，Schaudt和钟与我最近的工作黄和泽田意味着唯一剩下的未知情况是当H=P4+ nP 1的所有正整数n。除了这个二分法之外，我计划对各种图G和H，特别是G= 2 P2的临界（G，H）-自由图进行分类。这是由于许多图族包含相同的2 P2-free图的无限族。在这一领域的成功将导致新的多项式时间证明算法，这将是有用的着色算法，或新的高度结构化的临界图的无限家庭相应的复杂性二分法。技术将包括结构图理论和计算机搜索详尽生成的混合。动态图的一个突出模型是顶点（或边）以某种概率p随机独立地起作用。可靠性被定义为图具有某些感兴趣的属性的概率，例如与连通性，控制数和copnumber相关的属性。使图的可靠性最大化可以应用于电信、社交网络和网络安全。一个图是一致最可靠的（UMR），如果它在一个给定的家庭中的所有图中具有最大的可靠性。对UMR图进行分类可以设计最优网络，即使组件故障随时间变化也是如此。我计划继续使用组合和分析技术在各种可靠性模型下对UMR图进行分类。经典的结果分析理论的多项式（如定理由于高斯和卢卡斯，鲁什和莫比乌斯）预计有优雅的应用，因为他们在我以前的工作和其他工作的可靠性（如在工作布朗和科尔伯恩，罗伊尔和索卡尔和瓦格纳）。