The minimum dominating set problem remains NP-hard when restricted to any of the following graph classes: c -dense graphs, chordal graphs, 4-chordal graphs, weakly chordal graphs, and circle graphs. Developing and using a general approach, for each of these graph classes we present an exponential time algorithm solving the minimum dominating set problem faster than the best known algorithm for general graphs. Our algorithms have the following running time: O (1.4124 n ) for chordal graphs, O (1.4776 n ) for weakly chordal graphs, O (1.4845 n ) for 4-chordal graphs, O (1.4887 n ) for circle graphs, and O (1.2273
(1+√1−2
c
)
n ) for c -dense graphs.
7 February 2012 in Discrete Mathematics & Theoretical Computer Science
Graphs and Algorithms An independent dominating set D of a graph G = (V,E) is a subset of vertices such that every vertex in V \ D has at least one neighbor in D and D is an independent set, i.e. no two vertices of D are adjacent in G. Finding a minimum independent dominating set in a graph is an NP-hard problem. Whereas it is hard to cope with this problem using parameterized and approximation algorithms, there is a simple exact O(1.4423^n)-time algorithm solving the problem by enumerating all maximal independent sets. In this paper we improve the latter result, providing the first non trivial algorithm computing a minimum independent dominating set of a graph in time O(1.3569^n). Furthermore, we give a lower bound of \Omega(1.3247^n) on the worst-case running time of this algorithm, showing that the running time analysis is almost tight.
Les premiers algorithmes exacts exponentiels pour résoudre des problèmes NP-difficiles datent des années soixante. Ces dernières années ont vu un intérêt croissant pour la conception de tels algorithmes tout comme pour l'amélioration de la précision de l'analyse de leur temps d'exécution. Ils sont motivés par les larges applications de problèmes réputés difficiles et qui, sous l'hypothèse P 6= NP, n'admettent pas d'algorithme polynomial en calculant une solution exacte. Dans cette thèse on s'intéresse au problème classique de la domination dans un graphe. On étudie également plusieurs variantes et généralisations de ce problème fondamental. Nous proposons des algorithmes exponentiels pour déterminer un ensemble dominant de taille minimum sur les graphes c-denses, cordaux, 4-cordaux, faiblement cordaux, cercles et bipartis. Puis, nous étudions le problème de la clique dominante qui demande de trouver un ensemble dominant qui soit aussi une clique du graphe. Nous proposons un algorithme Brancher & Réduire qui détermine une clique dominante de taille minimum. L'analyse du temps d'exécution est réalisée en utilisant la technique Mesurer pour Conquérir. Nous donnons ensuite un algorithme général pour énumérer tous les ensembles ( %)-dominants d'un graphe en temps O(cn), avec c < 2, sous certaines conditions sur les ensembles et %, et établissons une borne supérieure combinatoire sur leur nombre. Finalement, nous nous intéressons à un problème de domination partielle et obtenons un algorithme pour le problème de la domination romaine. Grâce à un algorithme basé sur le paradigme de la Programmation Dynamique, nous proposons un algorithme pour le problème de la domination avec des puissances variables