Dominating Induced Matchings

摘要

We study the problem of determining whether or not a graph G has an induced matching that dominates every edge of the graph, which is also known as EFFICIENT EDGE DOMINATION. This problem is known to be NP-complete in general as well as in some restricted domains, such as bipartite graphs or regular graphs. In this paper, we identify a graph parameter to which the complexity of the problem is sensible and produce results of both negative (intractable) and positive (solvable in polynomial time) type.