Forbidding Induced Subgraphs: Decompositions, Coloring and Algorithms

禁止诱导子图：分解、着色和算法

• 批准号: 2348219
• 负责人: Maria Chudnovsky
• 金额: $ 36万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-06-01 至 2027-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2348219&HistoricalAwards=false
• 关键词: Forbidding; Induced; Subgraphs; Decompositions; Coloring; Forbidding; Induced; Subgraphs; Decompositions; Coloring

A basic question in mathematics is: how do we measure the complexity of an object? There is also an algorithmic analogue: for which objects can we solve hard problems efficiently? Having decided on the measure, one then asks: what information about the object guarantees that it can be classified as "uncomplicated" according to the chosen measure? "Treewidth" is a well-known measure of complexity in both structural and algorithmic graph theory. Many hard problems become tractable if the input graph is known to have small treewidth. Exhibiting a particular kind of a tree decomposition is also a useful way to describe the structure of a graph. This project studies the connections between the treewidth of a given graph and its local behavior. Graduate students will be involved in the project. The PI will also continue to popularize her work, and mathematics in general, through public lectures.This project intends to bring the powerful concepts of tree structures and non-crossing separations to the study of families of graphs defined by forbidden induced subgraphs. Several aspects of this program are outlined: from the familiar idea of upper-bounding the bag size, to tree-decompositions geared toward solving optimization problems, and applying tree-structures to the study of classical problems in graph theory. Different approaches are proposed for different possible applications. Progress on any of these aspects will advance the understanding of the structure of families of graphs defined by forbidden induced subgraphs, contribute to solutions of long-standing open problems, and have significant algorithmic consequences.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

数学中的一个基本问题是：我们如何衡量对象的复杂性？还有一个算法类似物：我们可以为哪些对象有效地解决难题？决定了该措施后，人们问：有关对象的哪些信息可以确保它可以根据所选措施将其归类为“简单”？ “树宽”是结构和算法图理论中复杂性的众所周知的度量。如果已知输入图具有较小的树宽，那么许多硬问题就会变得可行。表现出特定的树木分解也是描述图的结构的有用方法。该项目研究给定图的树宽及其局部行为之间的联系。研究生将参与该项目。 PI还将通过公开讲座继续推广她的作品和数学。该项目打算将树木结构和非交叉分离的强大概念带入对禁止诱导的子图定义的图形家庭的研究。概述了该程序的几个方面：从熟悉的袋子大小限制的概念，到针对解决优化问题的树木分类，以及将树结构应用于图理论中经典问题的研究。为不同的可能应用提出了不同的方法。在这些方面的任何一个方面的进展都将提高人们对被禁止的诱发子图定义的图形家庭结构的理解，促进了长期存在的开放问题的解决方案，并具有重大的算法后果。该奖项反映了NSF的法定任务，并通过评估该基金会的知识绩效和广泛的影响来评估NSF的法定任务，并被视为值得的支持。