Progress in Enumeration of Minimal Dominating Sets

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. 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.
  • 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.
  • 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.
  • We investigate the complexity of the enumeration of (inclusion-wise) minimal connected 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 connected dominating sets in split graphs, minimal total dominating sets in split graphs, minimal dominating sets in co-bipartite graphs .
  • We prove that line graphs and path graphs have bounded conformality. As a consequence, we obtain output-polynomial time algo- rithms for enumerating the set of minimal dominating sets of line graphs and path graphs. Therefore, there exists an output-polynomial time algorithm that enumerates the set of minimal edge-dominating sets of any graph.
  • We reduce (in polynomial time) the enumeration of minimal dominating sets in interval and permutation graphs to the enumeration of paths in DAGs. As a consequence, we can enumerate in linear delay, after a polynomial time pre-processing, minimal dominating sets in interval and permutation graphs. We can also count them in polynomial time. This improves considerably upon previously known results on interval graphs, and to our knowledge no output polynomial time algorithm for the enumeration of minimal dominating sets and their counting were known for permutation graphs.