Forbidding Induced Subgraphs: Decompositions, Coloring and Algorithms

Princeton University, Princeton NJ

Investigators

Abstract

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.