An $O^*(1.1939^n)$ time algorithm for minimum weighted dominating induced matching

MIN CHIH LIN; MICHEL MIZRAHI; JAYME L. SZWARCFITER

Hong Kong

Conferencia; ISAAC 2013 (24th International Symposium on Algorithms and Computation); 2013

The University of Hong Kong

Say that an edge of a graph $G$ dominates itself and every otheredge sharing a vertex of it. An edge dominating set of a graph $G=(V,E)$is a subset of edges $E´ subseteq E$ which dominates all edges of$G$. In particular, if every edge of $G$ is dominated by exactlyone edge of $E´$ then $E´$ is a dominating induced matching. It isknown that not every graph admits a dominating induced matching,while the problem to decide if it does admit it is NP-complete. In this paper we consider the problems of finding a minimum weighteddominating induced matching, if any, and counting the number ofdominating induced matchings of a graph with weighted edges. Wedescribe an exact algorithm for general graphs that runs in$O^*(1.1939^n)$ time and polynomial (linear) space, for solvingthese problems. This improves over the existing exact algorithmsfor the problems in consideration.