Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes
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+root 1-2c)n)) for c-dense graphs.
dominating set problem graph classes moderately exponential time algorithms