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.