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 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]. [Scribe Notes] [src]

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(knO(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).

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]

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.