
A dominating set D in a graph is a subset of its vertex set such that each vertex is either in D or has a neighbour in D. From [M.M. Kante, V. Limouzy, A. Mary and L. Nourine, On the Enumeration of Minimal Dominating Sets and Related Notions, SIDMA 28(4):1916–1929 (2014)] we know that the counting (resp. enumeration) of (inclusions-wise) minimal dominating sets is equivalent to the counting (resp. enumeration) of (inclusion-wise) minimal transversals in hypergraphs. The existence of an output-polynomial time algorithm for the enumeration of minimal dominating sets in graphs is open for a while, but by now for several graph classes it was shown that there is indeed an output-polynomial time algorithm. Since whenever we can count, we can enumerate in output-polynomial time, it is interesting to know for which graph classes one can count the set of minimal dominating sets in polynomial time (it is known that the problem is already \(\#P\)-complete in general graphs). In this manuscript we show that for many known graph classes with an output-polynomial time algorithm for the enumeration of minimal dominating sets, the counting version is \(\#P\)-complete, and for some of them a sub-exponential lower bound is also given (under \(\#\)ETH).
[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC]
[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC]
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
