parameterized complexity

When dealing with hard problems, problems which we are not able to solve in polynomial time, it is common practice to preprocess an instance to reduce its size and make the task of solving it easier. Parameterized Complexity offers a theoretical framework to prove the efficiency…

Most interesting optimization problems on graphs are NP-hard, implying that (unless P=NP) there is no polynomial time algorithm that solves all the instances of an NP-hard problem exactly. However, classical complexity measures the running time as a function of only the overall …

Parameterized complexity theory relaxes the classical notion of tractability and allows to solve some classically hard problems in a reasonably efficient way. However, many problems of interest remain intractable in the context of parameterized complexity. A completeness theory …