Reoptimization of parameterized problems
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.
- A 2k-kernelization algorithm for vertex cover based on crown decomposition
- A 2k-vertex kernel for maximum internal spanning tree
- A completeness theory for polynomial (Turing) kernelization
- A linear vertex kernel for maximum internal spanning tree
- A theory and algorithms for combinatorial reoptimization
- Crown structures for vertex cover kernelization
- Deterministic parameterized connected vertex cover
- Dynamic parameterized problems
- Dynamic parameterized problems and algorithms
- Finding odd cycle transversals.
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Fundamentals of parameterized complexity
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Introduction to algorithms.
- Kernel bounds for disjoint cycles and disjoint paths
- Kernel(s) for problems with no kernel
- Kernelization lower bounds through colors and IDs
- On finding directed trees with many leaves
- On problems without polynomial kernels
- On the Hardness of Reoptimization
- On the parameterized complexity of dynamic problems
- Parameterized algorithms
- Parametrized complexity theory.
- Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
- Reoptimizing the traveling salesman problem
- Scheduling with forbidden sets
- Spanning trees: A survey
- Vertex packings: Structural properties and algorithms
This page was built for publication: Reoptimization of parameterized problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2170282)
