Neighborhood inclusions for minimal dominating sets enumeration: linear and polynomial delay algorithms in $P_7$-free and $P_8$-free chordal graphs

Abstract

In [M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine. On the enumeration of minimal dominating sets and related notions. SIAM Journal on Discrete Mathematics, 28(4):1916-1929, 2014] the authors give an $O(n+m)$ delay algorithm based on neighborhood inclusions for the enumeration of minimal dominating sets in split and $P_6$-free chordal graphs. In this paper, we investigate generalizations of this technique to $P_k$-free chordal graphs for larger integers $k$. In particular, we give $O(n+m)$ and $O(n^3\cdot m)$ delays algorithms in the classes of $P_7$-free and $P_8$-free chordal graphs. As for $P_k$-free chordal graphs for $k\ge 9$, we give evidence that such a technique is inefficient as a key step of the algorithm, namely the irredundant extension problem, becomes NP-complete.

arXiv comment16 pages, 3 figures