[+] Parameterized Complexity II: ETH & Planar. Exponential Time Hypothesis (ETH), strong ETH, 3coloring, reduction size blowup, vertex cover, dominating set, Hamiltonicity, independent set, clique, planar 3SAT, planar graph problems, parameterized consequences of ETH, parameter blowup. Planar problems: Grid Tiling, list coloring, grid tiling with ≤, scattered set, independent set in unitdisk graphs.  
This lecture is about strong lower bounds on running time that are possible by assuming the Exponential Time Hypothesis: there is no 2^{o(n}) algorithm to solve nvariable 3SAT. This conjecture is a stronger form of P ≠ NP, and it lets us keep track of “problem size blowup”, something we've ignored before in our NPhardness reductions. Many of the reductions we've seen, such as 3coloring, vertex cover, dominating set, Hamiltonicity, and Independent Set/Clique have linear blowup, so we get 2^{o(n)} lower bounds. On the other hand, planar versions of these problems (except Clique) have quadratic blow up because of the crossover gadgets, so we get 2^{o(√n) lower bounds. } In parameterized complexity, we get a particularly strong form of FPT ≠ W[1]: there is no f(k) n^{o(k)} algorithm for Clique/Independent Set, for any computable function f. In particular, there's no f(k) n^{O(1)} (FPT) algorithm. By keeping track of the parameter blowup in our parameterized reductions, we can prove similar bounds for other problems, e.g. multicolored Clique/Independent Set, Dominating Set, Set Cover, and Partial Vertex Cover. Finally, we'll cover a useful base problem, called Grid Tiling, for proving W[1]hardness of problems on planar graphs or in 2D. Specifically, we'll use Grid Tiling to prove Scattered Set is W[1]hard in planar graphs, and that Independent Set is W[1]hard in in unitdisk graphs. These results also imply that these problems have no EPTAS.  
This class, we don't have any assigned lecture videos (or new lecture material), but we'll still bring a bunch of fun problems in complexity.  
Alas, this week's class will be the last one in which we solve problems! We have a bunch more new open problems, including a lot of fun video games. (No solved problems this week; if you don't want to work on open problems, work on your project!) In addition, I'll present the 1page slide summaries of the presentations to come in the final two class sessions.  
 

Handwritten notes, page 1/8 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/8 • [previous page] • [next page] • [PDF] 

Slides, page 1/19 •
[previous page] •
[next page] •
[PDF]
Slide from Lecture 9. Figure drawn by Erik based on http://dx.doi.org/10.1016/03043975(76)900591 Slides, page 1/19 • [previous page] • [next page] • [PDF] 