Tutorial: Recent Progress in the Structure of Large-Treewidth Graphs and Some Applications

Опубликовано 18 августа 2016, 21:03

Tree decompositions and treewidth play a key role in the seminal work of Robertson and Seymour on graph minors. One of their fundamental results is the Excluded-Grid Theorem which states that every graph G with treewidth at least k contains a f(k) x f(k) grid-minor for some (slowly growing) function f. Treewidth-based ideas have, over the years, yielded many algorithmic and structural results on graphs and related structures. There have been some recent advances in our understanding of the structure of graphs with large treewidth. These advances were partly motivated by the study of polynomial-time approximation algorithms for the maximum disjoint paths problem, culminating in a breakthrough by Chuzhoy in 2011. Subsequent work, building upon some of her ideas and other tools, has led to several new results including a polynomial relationship between treewidth of a graph and the size of its largest grid-minor. The tutorial will provide relevant background on treewidth, describe the highlights of recent developments, and a few applications.