An exact algorithm for the minimum dominating clique problem

A subset of vertices D subset of 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.3387(n)) 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 Omega(1.2599(n)) for the worst case running time of the algorithm. Finally using memorization we obtain an O(1.3234(n)) time and exponential space algorithm for the same problem. (c) 2007 Elsevier B.V. All rights reserved.