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. 338 7 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 Ω ( 1. 259 9 n ) for the worst case running time of the algorithm. Finally using memorization we obtain an O ( 1. 323 4 n ) time and exponential space algorithm for the same problem.

Authors

• Dieter Kratsch
• Mathieu Liedloff Université d'Orlèans

Keywords

• Graph algorithms
• Exponential time algorithms
• Dominating clique
• Dominating set