Explaining treewidth through the Traveling Salesman Problem, Tara Abrishami, GS (2278472)

I study a graph parameter called treewidth, which measures how easy or hard it is to solve problems on the graph. In this video, we explore treewidth by considering a problem called the Traveling Salesman Problem. The task of the Traveling Salesman Problem is to travel to each city in a specified group of cities while spending the least amount of money possible. This problem can be modeled as an abstract graph problem. The Traveling Salesman Problem is hard in general, but for certain graphs, i.e. graphs with small treewidth, it's easy. The focus of my research is determining which graphs have small treewidth. Many different problems can be solved easily in graphs with small treewidth, and these problems have a wide range of applications, making this an important topic of study.

Tara Abrishami, GS: math.princeton.edu/~taraa