A subset of vertices D is contained in 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 problem are NP-hard. We present an O(1.3390~n) time 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.2599~n) for the worst case running time of our algorithm.
展开▼
