Exact algorithms for dominating induced matching based on graph partition

摘要

A dominating induced matching, also called an efficient edge domination, of a graph G = (V, E) with n = vertical bar V vertical bar vertices and m = vertical bar E vertical bar edges is a subset F subset of E of edges in the graph such that no two edges in F share a common endpoint and each edge in E F is incident with exactly one edge in F. It is NP-hard to decide whether a graph admits a dominating induced matching or not. In this paper, we design a 1.1467(n)n(0(1)) -time exact algorithm for this problem, improving all previous results. This problem can be redefined as a partition problem that is to partition the vertex set of a graph into two parts I and F, where I induces an independent set (a 0-regular graph) and F induces a perfect matching (a 1-regular graph), After giving several structural properties of the problem, we show that the problem always contains some "good vertices," branching on which by including them to either I or F we can effectively reduce the graph. This leads to a fast exact algorithm to this problem. (C) 2015 Elsevier B.V. All rights reserved.