Lesson plan
Parameterized complexity
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. Then the theory analyses how the running time (or space) for solutions to the problem behave as the parameters get larger. To illustrate the idea, the for a fixed k we can solve instances of vertex cover problem (vertices cover edges) in linear time, whereas the only known algorithms for dominating set problem (vertices cover vertices) is more or less search all possible size k subsets and hence require about Ω(n^k) time. When this idea is made formal, the first behaviour is called fixed parameter tractability, since, although both are polynomial time algorithms, the former is of the form O(n^c) independent of the parameter, and the latter is of the form Ω(n^{f(k)). Researchers had often studied restrictions of problems by restricting parameters such as maximum vertex degree, cutwidth, treewidth, or genus. Several authors had noted that there might be a general method of attacking intractability obtained through understanding the complexity as a function of parameters, including Vardi (in the context of databases) and Regan (in finite model theory).…
Article summary
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. Then the theory analyses how the running time (or space) for solutions to the problem behave as the parameters get larger. To illustrate the idea, the for a fixed k we can solve instances of vertex cover problem (vertices cover edges) in linear time, whereas the only known algorithms for dominating set problem (vertices cover vertices) is more or less search all possible size k subsets and hence require about Ω(n^k) time. When this idea is made formal, the first behaviour is called fixed parameter tractability, since, although both are polynomial time algorithms, the former is of the form O(n^c) independent of the parameter, and the latter is of the form Ω(n^{f(k)). Researchers had often studied restrictions of problems by restricting parameters such as maximum vertex degree, cutwidth, treewidth, or genus. Several authors had noted that there might be a general method of attacking intractability obtained through understanding the complexity as a function of parameters, including Vardi (in the context of databases) and Regan (in finite model theory).…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.