Extension of some edge graph problems: Standard, parameterized and approximation complexity

International audience ; We consider extension variants of some edge optimization problems in graphs containing the classical Edge Cover, Matching, and Edge Dominating Set problems and generalizations thereof. Given a graph G = (V, E) and an edge set U ⊆ E, it is asked whether there exists an inclusion-wise minimal (or maximal, respectively) feasible solution E which satisfies a given property, for instance, being an edge dominating set (or a matching, respectively) and containing the forced edge set U (or avoiding any edges from the forbidden edge set E \ U , respectively). We present hardness results for these problems, for restricted instances such as bipartite or planar graphs. We counterbalance these negative results with parameterized complexity results. We also consider the price of extension, a natural optimization problem variant of extension problems, leading to some approximation and inapproximability results.