Parameterized complexity

Common card · No. 484964

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...

Read on Wikipedia