Parameterized Complexity and Exact Algorithms

We study problems such as:

• Travelling Salesman Problem: given a graph (=network) with n vertices (=nodes), what is the shortest route passing by all vertices?

• Steiner Tree: given a graph with n nodes and t terminals, along with costs for connecting two given vertices, what is the cheapest way to connect all terminals?

• Graph Colouring: for n tasks, with a list of pairs that cannot be performed simultaneously, how many timeslots do we need to perform all of them?

There is typically a parameter that describes the input size (e.g. n in the problems above) and we would like to know how efficiently we can solve the problem in terms of n. We often view 'polynomial in n' as efficient, but for the problems above such algorithms are not known (and do not exist unless P=NP). 

So what can we do, if we do want to always receive the correct answer?

• We may still want to know the boundaries of what is possible. For example, if the problem can be solved in time about 2^n, can it also be solved in time about 1.999^n?

• When we have more information on the input, we may be able to solve the problem more efficiently. For example, perhaps certain types of substructures are promised not to appear ('H-free graphs') or the graph corresponds to a road networks and so can be drawn on the plane without crossing ('planar graphs').

In parameterized complexity, this is taken one step further and we study the running time not just in terms of the input size, but also in terms of another parameter. This parameter can be, for example, the number of terminals t in Steiner Tree, the number of timeslots/colours in Graph Colouring or a parameter of the input capturing 'how much the network looks like a tree' (treewidth). There are no broadly three possibilities:

• Even when the parameter is small, the problem remains NP-hard (unlikely to be solvable in polynomial time).

• XP: there is a polynomial time algorithm whenever the parameter is constant. This allows an algorithm with running time n^{k} for example, for n the input size and k the parameter. 

• FPT (fixed parameter tractable): there is a polynomial time algorithm whenever the parameter is constant, and the exponent of the polynomial does not grow with the parameter. This means n^{k} is not allowed, but for example 2^k n^2 is fine. 

The idea is that the parameter k is much smaller than the input size n, but still we may want to find the optimal dependence both in terms of k and n. 

We can give upper bounds on the running time by providing an algorithm. Unfortunately, we have no idea on how to prove lower bounds, and instead prove claims of the form 'if problem X can be solved in polynomial time, then so can problem Y'. This allows one to define complexity classes of problems that are all 'equally hard' in some way. Moreover, we can also provide exact lower bounds on the running time by assuming exact bounds for one problem. For example, the Exponential Time Hypothesis typically allows to exclude subexponential running times (e.g. 'Problem X cannot be solved in time 2^{o(n)}' or 'cannot be solved in time 2^{o(k)}n') whereas the Strong Exponential Time Hypothesis may even allow to pinpoint the base constant ('Problem X cannot be solved in time 1.9999^n') .