While many popular algorithms work in polynomial time, most of the natural problems are NP-hard, i.e., (most probably) they do not admit poly-time algorithms. This course is dedicated to approaches that overcome the NP-hardness barrier while still retaining provable guarantees on the algorithm.
Parameterized complexity achieves this by introducing another measure of the input called the parameter. The running time of the algorithm is then measured as some function of the parameter k and the input size n. The main target of the theory is a fixed-parameter tractable (FPT) algorithm, working in time f(k) · poly(n) for some function f of k. In practice, the dependency is often single-exponential in k and linear in n, leading to algorithms that are quite efficient as long as k is reasonably small. For example, while the Vertex Cover problem is NP-hard on general graphs, it admits an FPT algorithm running in time O(1.2738k + k · n), where k is the size of the vertex cover – which is still practical for pretty large graphs with a vertex cover of size up to 190.
In fact, the parameter needs not to be the solution size or something similarly explicit in the input, but rather could be an arbitrary property of the instance. A prominent example is the treewidth of a graph, which intuitively measures how tree-like the graph is. There are however, many other width measures capturing other structural properties of graphs, and in general many other ways to exploit the parameterized viewpoint to achieve tractability for a generally hard problem. A large portion of the course will be dedicated to parameterized complexity and various popular problems and parameters therein.
We will also cover a few approximation algorithms, which work in polynomial time on all inputs, but provide the solution that is only optimal up to some factor. Finally, we will touch on parameterized approximation – a combination of both approaches that is particularly useful for applications where a small error is non-critical/unavoidable, such as clustering of points with real-valued coordinates.
