2014/07/08 by Kanté, Mamadou Moustapha, Limouzy, Vincent, Mary, Arnaud +1 · 1 citation
#05C30 #05C69 #05C85 #68R05 #68R10 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.0 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2
paper · doi:10.48550/arxiv.1407.2053
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. In this paper, we are interested in the enumeration of (inclusion-wise) minimal dominating sets in graphs, called the Dom-Enum problem. It is well known that this problem can be polynomially reduced to the Trans-Enum problem in hypergraphs, i.e., the problem of enumerating all minimal transversals in a hypergraph. Firstly we show that the Trans-Enum problem can be polynomially reduced to the Dom-Enum problem. As a consequence there exists an output-polynomial time algorithm for the Trans-Enum problem if and only if there exists one for the Dom-Enum problem. Secondly, we study the Dom-Enum problem in some graph classes. We give an output-polynomial time algorithm for the Dom-Enum problem in split graphs, and introduce the completion of a graph to obtain an output-polynomial time algorithm for the Dom-Enum problem in P6-free chordal graphs, a proper superclass of split graphs. Finally, we investigate the complexity of the enumeration of (inclusion-wise) minimal connected dominating sets and minimal total dominating sets of graphs. We show that there exists an output-polynomial time algorithm for the Dom-Enum problem (or equivalently Trans-Enum problem) if and only if there exists one for the following enumeration problems: minimal total dominating sets, minimal total dominating sets in split graphs, minimal connected dominating sets in split graphs, minimal dominating sets in co-bipartite graphs.