Reoptimization of parameterized problems

Autor: Hans-Joachim Böckenhauer, Elisabet Burjons, Martin Raszyk, Peter Rossmanith
Rok vydání: 2021
Předmět:
Zdroj: Acta informatica, 59 (4)
Acta informatica 59(4), 427-450 (2022). doi:10.1007/s00236-022-00428-y special issue: "Special Issue: Klaus-Jörn Lange Festschrift / Issue editors: Henning Fernau, Markus Holzer, Petra Wolf"
ISSN: 0001-5903
1432-0525
DOI: 10.1007/s00236-022-00428-y
Popis: 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}$. 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 $\mathbf{2k + 1}$ using crown decompositions only, which improves the size of the kernel achievable with this technique in the classic problem.
Acta informatica, 59 (4)
ISSN:0001-5903
ISSN:1432-0525
Databáze: OpenAIRE
Externí odkaz: