151. On the complexity of solution extension of optimization problems
- Author
-
Mehdi Khosravian Ghadikolaei, Florian Sikora, Henning Fernau, Katrin Casel, and Jérôme Monnot
- Subjects
FOS: Computer and information sciences ,Vertex (graph theory) ,Discrete mathematics ,Optimization problem ,General Computer Science ,Degree (graph theory) ,Bin packing problem ,Computer science ,010102 general mathematics ,0102 computer and information sciences ,Computational Complexity (cs.CC) ,01 natural sciences ,Planarity testing ,Theoretical Computer Science ,Computer Science - Computational Complexity ,010201 computation theory & mathematics ,Dominating set ,Graph (abstract data type) ,0101 mathematics ,Time complexity - Abstract
The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal dominating sets of a graph $G=(V,E)$, one usually arrives at the problem to decide for a vertex set $U \subseteq V$, if there exists a \textit{minimal} dominating set $S$ with $U\subseteq S$. We propose a general, partial-order based formulation of such extension problems and study a number of specific problems which can be expressed in this framework. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimisation problem can be solved in polynomial time. This raises the question of how fixing a partial solution causes this increase in difficulty. In this regard, we study the parameterised complexity of extension problems with respect to parameters related to the partial solution, as well as the optimality of simple exact algorithms under the Exponential-Time Hypothesis. All complexity considerations are also carried out in very restricted scenarios, be it degree restrictions or topological restrictions (planarity) for graph problems or the size of the given partition for the considered extension variant of Bin Packing.
- Published
- 2022