On the complexity of the dominating induced matching problem in hereditary classes of graphs

Cardoso, Domingos M.; Korpelainen, Nicholas and Lozin, Vadim V. (2011). On the complexity of the dominating induced matching problem in hereditary classes of graphs. Discrete Applied Mathematics, 159(7) pp. 521–531.

DOI: https://doi.org/10.1016/j.dam.2010.03.011

Abstract

The dominating induced matching problem, also known as efficient edge domination, is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This problem is known to be NP-complete. We study the computational complexity of the problem in special graph classes. In the present paper, we identify a critical class for this problem (i.e., a class lying on a “boundary” separating difficult instances of the problem from polynomially solvable ones) and derive a number of polynomial-time results. In particular, we develop polynomial-time algorithms to solve the problem for claw-free graphs and convex graphs.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI