Forbidding Induced Subgraphs: Decompositions, Coloring and Algorithms

数学中的一个基本问题是：我们如何衡量一个对象的复杂性？还有一个类似的算法：对于哪些对象，我们可以有效地解决难题？在确定了度量标准之后，人们接着问：关于对象的什么信息保证它可以根据所选择的度量标准被归类为“不复杂的”？“树宽”是结构和算法图论中众所周知的复杂性度量。如果已知输入图具有小的树宽，许多困难的问题变得易于处理。展示一种特殊的树分解也是描述图的结构的一种有用的方法。这个项目研究给定图的树宽和它的局部行为之间的联系。研究生将参与该项目。PI还将继续通过公开讲座推广她的工作和数学。该项目旨在将树结构和非交叉分离的强大概念引入到由禁止诱导子图定义的图族的研究中。概述了该计划的几个方面：从熟悉的袋大小上界的想法，到面向解决优化问题的树分解，以及将树结构应用于图论经典问题的研究。针对不同的可能应用提出了不同的方法。任何这些方面的进展将推进对由禁止诱导子图定义的图族结构的理解，有助于解决长期存在的开放问题，并具有重要的算法后果。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

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.