Abstract

Tree-width is a property that measures the similarity of a graph with a tree. Recent years have seen many important applications of tree-width in algorithm design and complexity theory, as it turns out that many NP-hard decision and optimisation problems are solvable in polynomial time when restricted to graphs whose tree-width is bounded by some constant.

While it is hard to compute the tree-width of an arbitrary graph, it turns out there are some nice combinatorial games that allow us to establish upper bounds on tree-width on restricted classes of graphs.

Also, people have recently discovered some novel applications of tree-width to the study of Java module systems, metarouting algorithms, categorical type theory, operational semantics, and concurrency in programming languages. So if you are working in one of those areas, you better make sure you don’t miss this talk.