Search

• Definition and study of the extension variants of the connected vertex cover problem (Ext-CVC), and of the Non-Separating Independent Set problem (Ext-NSIS). • Solvability and hardness results for Ext-CVC , notably in bipartite graphs of maximum degree 3 and in weakly triangulated graphs, applying also to Ext-NSIS. • Formulation of the concept of Price of Extension (PoE) as the approximation ratio for the problem Max Ext-CVC (resp., Min Ext-NSIS). • Lower bounds for PoE of Max Ext-CVC in general and bipartite graphs; proof that it is equal to 1 in chordal graphs, carrying over to Min Ext-NSIS. We consider extension variants of Vertex Cover and Independent Set , following a line of research initiated in [10]. In particular, we study the Ext-CVC and the Ext-NSIS problems: given a graph G = (V , E) and a vertex set U ⊆ V , does there exist a minimal connected vertex cover (respectively, a maximal non-separating independent set) S , such that U ⊆ S (respectively, U ⊇ S). We present hardness results for both problems, for certain graph classes such as bipartite, chordal and weakly chordal. To this end we exploit the relation of Ext-CVC to Ext-VC , that is, to the extension variant of Vertex Cover. We also study the Price of Extension (PoE) , a measure that reflects the distance of a vertex set U to its maximum efficiently computable subset that is extensible to a minimal connected vertex cover, and provide negative and positive results for PoE in general and special graphs. [ABSTRACT FROM AUTHOR]

A solution extension problem consists in an instance and a partial feasible solution which is given in advance and the goal is to extend this partial solution to a feasible one. Many well-known problems like Coloring Extension Problems, Traveling Salesman Problem and Routing problems, have been studied in this framework. In this paper, we focus on the edge-weighted spanning star forest problem for both minimization and maximization versions. The goal here is to find a vertex partition of an edge-weighted graph into disjoint non-trivial stars and the value of a solution is given by the sum of the edge-weights of the stars. We propose NP -hardness, parameterized complexity, positive and negative approximation results. • An extension variant of the weighted edge cover problem is studied. • The problem is NP -complete in complete graphs while polynomial solvable in bounded tree-width graphs. • For non-negative weights, the minimization version is in-approximable at all while the maximization version is in RAPX. • If weight function satisfies (extended) c -relaxed triangle inequalities, the minimization version is in RAPX. [ABSTRACT FROM AUTHOR]

We study the approximability of the NP-complete Maximum Minimal Feedback Vertex Set problem. Informally, this natural problem seems to lie in an intermediate space between two more well-studied problems of this type: Maximum Minimal Vertex Cover , for which the best achievable approximation ratio is n , and Upper Dominating Set , which does not admit any n 1 − ϵ approximation. We confirm and quantify this intuition by showing the first non-trivial polynomial time approximation for Maximum Minimal Feedback Vertex Set with a ratio of O (n 2 / 3) , as well as a matching hardness of approximation bound of n 2 / 3 − ϵ , improving the previously known hardness of n 1 / 2 − ϵ. Having settled the problem's approximability in polynomial time, we move to the context of super-polynomial time. We devise a generalization of our approximation algorithm which, for any desired approximation ratio r , produces an r -approximate solution in time n O (n / r 3 / 2). This time-approximation trade-off is essentially tight under the ETH. [ABSTRACT FROM AUTHOR]

• Extending a partial solution of an optimization problem occurs as a subproblem in many areas. • We propose a general framework for dealing with these extension problems. • We present several problems from different areas which can be expressed in this framework. • We show NP-hardness results and parameterized complexity results for the presented problems. 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 vertex covers of a graph G = (V , E) , one usually arrives at the problem to decide for a vertex set U ⊆ V (pre-solution), if there exists a minimal vertex cover S (i.e., a vertex cover S ⊆ V such that no proper subset of S is a vertex cover) with U ⊆ S (minimal extension of U). We propose a general, partial-order based formulation of such extension problems which allows to model parameterization and approximation aspects of extension, and also highlights relationships between extension tasks for different specific problems. As examples, we study a number of specific problems which can be expressed and related in this framework. In particular, we discuss extension variants of the problems dominating set and feedback vertex/edge set. All these problems are shown to be NP -complete even when restricted to bipartite graphs of bounded degree, with the exception of our extension version of feedback edge set on undirected graphs which is shown to be solvable in polynomial time. For the extension variants of dominating and feedback vertex set, we also show NP -completeness for the restriction to planar graphs of bounded degree. As non-graph problem, we also study an extension version of the bin packing problem. We further consider the parameterized complexity of all these extension variants, where the parameter is a measure of the pre-solution as defined by our framework. [ABSTRACT FROM AUTHOR]