Polynomial Space Algorithms for Counting Dominating Sets and the Domatic Number

摘要

Inclusion/exclusion and measure and conquer are two of the most important recent new developments in the field of exact exponential time algorithms. Algorithms that combine both techniques have been found very recently, but thus far always use exponential space. In this paper, we try to obtain fast exponential time algorithms for graph domination problems using only polynomial space. Using a novel treewidth based annotation procedure to deal with sparse instances, we give an algorithm that counts the number of dominating sets of each size k in a graph in O(1.5673~n) time and polynomial space. We also give an algorithm for the domatic number problem running in O(2.7139~n) time and polynomial space.