# 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] [Accessibility]

## Lecture 13 Video     [previous] [next]

 [+] Parameterized Complexity I: W Hierarchy. Parameter, parameterized problem, XP, fixed-parameter tractable (FPT), Vertex Cover, EPTAS, parameterized reduction. W[1]: k-step nondeterministic Turing machine, Independent Set, clique in regular graphs, partial vertex cover, multicolored clique, shortest common supersequence, Flood-It on trees. W[2]: dominating set, set cover. W hierarchy: depth, weft, Weighted Circuit SAT, W[P], W[t], W[*], W[1], W[2], W[SAT]. This lecture begins our analysis of decision problems from a parameterized perspective, where we consider the dependence on an arbitrary parameter k in addition the problem size n. The algorithmic goal is to confine the exponential dependence to the parameter k instead of the problem size n. In this way, we get a deeper understanding of when the exponential time is reasonable (i.e. when k is small). More precisely, a problem is fixed-parameter tractable (FPT) if we can solve it in f(k) nO(1), for any function f(k), and constant O(1) independent of k. By contrast, a time bound of nf(k) is considered bad (but it has its own complexity class, XP). We'll introduce classes W[1] and W[2] conjectured to be distinct from FPT, by analogy to P ≠ NP. Then we'll see several problems that are complete in this classes, under a new reduction type called parameterized reduction. Specifically, k-step nondeterministic Turing machine is the canonical hard problem for W[1]. We'll prove that it's equivalent to Independent Set, and use that to prove W[1]-hardness of clique/independent set in regular graphs, partial vertex cover, and a useful base problem called multicolored independent set. We'll also see a reduction from the W[1]-hard problem shortest common supersequence to a puzzle game called Flood-It on trees. For W[2], the typical starting problems are Dominating Set and Set Cover. We'll show that these problems are at least as hard as W[1] by a reduction from multicolored independent set. Finally, we'll define the general W hierarchy in terms of the depth and weft of circuits and a problem called Weighted Circuit SAT (which could also be called Circuit k-Ones).
 No support for video detected. Please use an HTML5 browser. 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/8 • [previous page] • [next page] • [PDF] Slides, page 1/8 • [previous page] • [next page] • [PDF]