Extension of Some Edge Graph Problems: Standard and Parameterized Complexity

摘要

We consider extension variants of some edge optimization problems in graphs containing the classical Edge Cover, Matching, and Edge Dominating Set problems. Given a graph G = (V, E) and an edge set U ⊆ E, it is asked whether there exists an inclusion-wise minimal (resp., maximal) feasible solution E' which satisfies a given property, for instance, being an edge dominating set (resp., a matching) and containing the forced edge set U (resp., avoiding any edges from the forbidden edge set EU). 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 results.