A Polynomial-time Algorithm for the Dominating Induced Matching Problem in the Class of Convex Graphs

The dominating induced matching problem is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This is known to be NP-complete in general. We develop a polynomial-time algorithm to solve the problem for convex graphs.