[+] Parameterized Complexity I: W Hierarchy. Parameter, parameterized problem, XP, fixedparameter tractable (FPT), Vertex Cover, EPTAS, parameterized reduction. W[1]: kstep nondeterministic Turing machine, Independent Set, clique in regular graphs, partial vertex cover, multicolored clique, shortest common supersequence, FloodIt 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 fixedparameter tractable (FPT) if we can solve it in f(k) n^{O(1)}, for any function f(k), and constant O(1) independent of k. By contrast, a time bound of n^{f(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, kstep 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 FloodIt 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 kOnes). 
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.