Forbidding Induced Subgraphs: Decompositions, Coloring and Algorithms

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

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.