An incremental polynomial time algorithm to enumerate all minimal edge dominating sets (Q494806)

Let \(G=(V, E)\) be a graph. For every vertex \(v\in V\), the open neighborhood of \(v\), \(N(v)\) is the set \(\{u\in V\mid uv\in E\}\) and the closed neighborhood of \(v\) is \(N[v]=N(v)\cup\{v\}\). For \(S\subseteq V(G)\), the open neighborhood and the closed neighborhood of \(S\) are \(N(S)=N_G(S)=\bigcup_{v\in S} N(v)\) and \(N[S]=N_G[S]=N(S)\cup S\), respectively. A set \(D\) of vertices is a dominating set of \(G\) if \(N[D]=V\). A dominating set is minimal if no proper subset of it is a dominating set. A set of edges \(A\subseteq E\) is an edge dominating set if each edge \(e\in E\) is either in \(A\) or is adjacent to an edge in \(A\). An edge dominating set is minimal if no proper subset of it is an edge dominating set. Enumeration of minimal dominating sets in graphs has recently been shown to be equivalent to enumeration of minimal transversals in hypergraphs. The question whether the minimal transversals of a hypergraph can be enumerated in output polynomial time is a fundamental and challenging question; it has been open for several decades and has triggered extensive research. In this paper, the authors show that all minimal edge dominating sets of a graph can be generated in incremental polynomial time. Also they present an algorithm that solves the equivalent problem of enumerating minimal (vertex) dominating sets of line graphs in incremental polynomial, and consequently output polynomial, time. Also all minimal dominating sets of a graph of girth at least 7 can be enumerated in incremental polynomial time. They give algorithms where the time delay between two consecutively generated minimal dominating sets on line graphs and on graphs of girth at least 7.