Reoptimization of parameterized problems

Area of Science:

• Theoretical Computer Science
• Computational Complexity Theory

Background:

• Parameterized complexity analyzes algorithms based on a parameter.
• Reoptimization seeks solutions for modified problem instances.
• Combining these offers new insights into problem complexity.

Purpose of the Study:

• To investigate the interplay between parameterized complexity and reoptimization.
• To classify the complexity of compositional problems under reoptimization.
• To identify conditions under which polynomial kernels emerge or are refuted.

Main Methods:

• Analysis of compositional problems within the parameterized reoptimization framework.
• Exploration of local modifications and their impact on kernelization.
• Application of techniques like crown decompositions for specific problems.

Main Results:

• Some compositional problems gain polynomial kernels under specific reoptimization local modifications.
• Other local modifications do not yield polynomial kernels, even under standard assumptions.
• The reoptimization of Connected Vertex Cover lacks a polynomial kernel unless Set Cover has a polynomial compression.
• The reoptimization of Vertex Cover achieves a smaller polynomial kernel using crown decompositions.

Conclusions:

• Reoptimization can alter the parameterized complexity landscape of problems.
• The existence of polynomial kernels is sensitive to the type of modification in reoptimization.
• This research refines the understanding of kernelization for parameterized problems.