6.889: Algorithms for Planar Graphs and Beyond (Fall 2011)

Erik Demaine, Shay Mozes, Christian Sommer, Siamak Tazari


[Home] [Problem Sets] [Project] [Lectures] [Problem Session Notes] [Klein's Book] [Accessibility]

Lecture 7 Video     [previous] [next]

[+] Treewidth and parameterized complexity.

In this lecture we introduce treewidth - one of the most central concepts in obtaining fast algorithms and approximation schemes for NP-hard problems. Indeed, a recurring theme in approximation schemes is to reduce the problem to an instance of small treewidth, while not losing too much, and then solve the problem exactly on that instance. We study treewidth, pathwidth, and some of their most fundamental properties.

Treewidth is a natural parameter of a graph and as we will see, if a graph has small treewidth, then we can solve a large number of NP-hard problems efficiently - regardless of the size of the graph. This takes us to the realm of parameterized complexity theory where we study problems not just with regard to the input size but together with a parameter. The goal is to find algorithms where we confine the exponential behavior to the parameter and remain efficient in the input size; hence, when the parameter is small, we still obtain very good algorithms. Another goal is to develop a robust negative theory that allows us to show that, in all likelihood, certain parameterized problems do not admit efficient algorithms in this sense.

Download Video: 360p, 720p

Lecture notes, page 1/11[previous page][next page][PDF]

Lecture notes, page 1/11[previous page][next page][PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.