Reoptimization of parameterized problems
Acta Informatica, vol. 59, pp. 427–450
Abstract
Abstract Parameterized complexity allows us to analyze the time complexity of problems with respect to a natural parameter depending on the problem. Reoptimization looks for solutions or approximations for problem instances when given solutions to neighboring instances. We combine both techniques, in order to better classify the complexity of problems in the parameterized setting. Specifically, we see that some problems in the class of compositional problems, which do not have polynomial kernels under standard complexity-theoretic assumptions, do have polynomial kernels under the reoptimization model for some local modifications. We also observe that, for some other local modifications, these same problems do not have polynomial kernels unless $$\mathbf{NP}\subseteq \mathbf{coNP/poly}$$ NP ⊆ coNP / poly . We find examples of compositional problems, whose reoptimization versions do not have polynomial kernels under any of the considered local modifications. Finally, in another negative result, we prove that the reoptimization version of Connected Vertex Cover does not have a polynomial kernel unless Set Cover has a polynomial compression. In a different direction, looking at problems with polynomial kernels, we find that the reoptimization version of Vertex Cover has a polynomial kernel of size $$\varvec{2k+1}$$ 2 k + 1 using crown decompositions only, which improves the size of the kernel achievable with this technique in the classic problem.
Authors 4
-
Hans-Joachim Böckenhauer corresponding
Affiliation as printed
Department of Computer Science, ETH Zurich, Universitätsstrasse 6, Zurich, 8092 Switzerland
Department of Computer Science, ETH Zurich, Universitätsstrasse 6, Zurich, 8092, Switzerland
-
Affiliation as printed
Department of Computer Science, RWTH Aachen, Ahornstrasse 55, Aachen, 52074 NRW Germany
Department of Computer Science, RWTH Aachen, Ahornstrasse 55, Aachen, 52074, NRW, Germany
-
Martin Raszyk corresponding
Affiliation as printed
Department of Computer Science, ETH Zurich, Universitätsstrasse 6, Zurich, 8092 Switzerland
Department of Computer Science, ETH Zurich, Universitätsstrasse 6, Zurich, 8092, Switzerland
-
Affiliation as printed
Department of Computer Science, RWTH Aachen, Ahornstrasse 55, Aachen, 52074 NRW Germany
Department of Computer Science, RWTH Aachen, Ahornstrasse 55, Aachen, 52074, NRW, Germany
Cited by 8 stored of 9
8 results
No patents citing this paper on Lens.org (checked 2026-10-06).