An exact algorithm for the minimum dominating clique problem

A subset of vertices D⊆V of a graph G=(V,E) is a dominating clique if D is a dominating set and a clique of G. The existence problem ‘Given a graph G, is there a dominating clique in G?’ is NP-complete, and thus both the Minimum and the Maximum Dominating Clique problems are NP-hard. We present an O(1.3387n) time and polynomial space algorithm that for an input graph on n vertices either computes a minimum dominating clique or reports that the graph has no dominating clique. The algorithm uses the Branch & Reduce paradigm and its time analysis is based on the Measure & Conquer approach. We also establish a lower bound of Ω(1.2599n) for the worst case running time of the algorithm. Finally using memorization we obtain an O(1.3234n) time and exponential space algorithm for the same problem.