Lecture notes, page 1/11 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/11 • [previous page] • [next page] • [PDF]
[+] 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. |
|
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.