Opening Complexity: Fixed-Parameter Algorithms
Complexity: Fixed-Parameter Algorithms
- Length
- 1 h 18 min
- Level
- Graduate
- Recorded
- MIT2016
Chapter 1 of 9: Before the lecture
Demaine solves vertex cover by branching on edge endpoints in single exponential time, then builds a quadratic kernel.
Fixed-parameter algorithms solve NP-hard problems exactly by confining the exponential part of the running time to a parameter . Demaine starts from brute force over all -subsets, which puts in the exponent, and defines fixed-parameter tractability to separate the two dependencies. A bounded search tree, branching on which endpoint of an edge joins the cover, solves vertex cover in single exponential time. Reduction rules for loops, multiedges and vertices of degree above cut any instance to a quadratic kernel; combining both techniques gives a faster algorithm. Demaine shows that a problem is FPT exactly when it admits a polynomial-time kernelization, and that an efficient polynomial-time approximation scheme implies an FPT decision algorithm. Session 20 of MIT 6.046J assumes NP-completeness and earlier vertex cover lectures.
Fixed-parameter algorithms solve NP-hard problems exactly by confining the exponential part of the running time to a parameter . Demaine starts from brute force over all -subsets, which puts in the exponent, and defines fixed-parameter tractability to separate the two dependencies. A bounded search tree, branching on which endpoint of an edge joins the cover, solves vertex cover in single exponential time. Reduction rules for loops, multiedges and vertices of degree above cut any instance to a quadratic kernel; combining both techniques gives a faster algorithm. Demaine shows that a problem is FPT exactly when it admits a polynomial-time kernelization, and that an efficient polynomial-time approximation scheme implies an FPT decision algorithm. Session 20 of MIT 6.046J assumes NP-completeness and earlier vertex cover lectures.

This lecture
Lecture 20 of 27 of Design and Analysis of Algorithms.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in