6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall '14)

Prof. Erik Demaine     TAs: Sarah Eisenstat, Jayson Lynch

[Home] [Lectures] [Problem Sets] [Project] [Open Problems] [Piazza]

Lecture 14 Video     [previous] [next]

[+] Parameterized Complexity II: ETH & Planar. Exponential Time Hypothesis (ETH), strong ETH, 3-coloring, 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 unit-disk graphs. [Scribe Notes] [src]

This lecture is about strong lower bounds on running time that are possible by assuming the Exponential Time Hypothesis: there is no 2o(n) algorithm to solve n-variable 3SAT. This conjecture is a stronger form of P ≠ NP, and it lets us keep track of “problem size blow-up”, something we've ignored before in our NP-hardness reductions. Many of the reductions we've seen, such as 3-coloring, vertex cover, dominating set, Hamiltonicity, and Independent Set/Clique have linear blow-up, so we get 2o(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 2o(√n) lower bounds.

In parameterized complexity, we get a particularly strong form of FPT ≠ W[1]: there is no f(kno(k) algorithm for Clique/Independent Set, for any computable function f. In particular, there's no f(knO(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 unit-disk graphs. These results also imply that these problems have no EPTAS.

Download Video: 360p, 720p

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/​0304-3975(76)90059-1

Slides, page 1/19[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 handwritten notes and slides should advance automatically. If you have any trouble with playback, email Erik.