Reoptimization of parameterized problems (Q2170282)

The current paper studies a combined approach of parameterised complexity theory and reoptimisation. Formally, parameterised problems are tuples \((x,k)\) of instances \(x\) together with a corresponding parameter value \(k\). Often, but not necessarily, the parameter is a natural number. In this context, one strives to find algorithms that solve such problems for any instance \((x,k)\) in time \(f(k)\cdot n^{O(1)}\) for a computable function \(f\); in such a case, the problem is called fixed-parameter tractable. This captures the observation that for very slowly growing or even constant parameters, the running time is very close to or equal to a polynomial. In the field of reoptimisation, one tries to find a solution to a given problem that is ``close'' to solutions of so-called neighbour instances. This concept is sometimes related to kernelization, which is also a way of obtaining fixed-parameter tractable algorithms for parameterised problems. The authors study several types of graph problems in this setting. Most of the results presented are negative, in the form of otherwise unlikely complexity class containments, such as \(\mathbf{NP}\subseteq\mathbf{coNP}/\mathbf{poly}\). The only positive result (Theorem 14) is of the form that the reoptimisation version for edge addition in \textsc{Vertex-Cover} has a polynomial reoptimisation kernel of size \(2k+1\), which can be constructed using well-known crown decompositions [\textit{W. Li} and \textit{B. Zhu}, Theor. Comput. Sci. 739, 80--85 (2018; Zbl 1395.68154)]. The paper is well written and helpful as a toolbox for problems for which such kernels do not exist, and shows interesting ideas on how to combine the above research areas in a meaningful way.