Enumerating Minimal Dominating Sets and Variants in Chordal Bipartite Graphs

Hypergraphs are encountered in countless areas of computer science or discrete mathematics. Formally, they consist of a pair $\mathscr{H}=(V(\mathscr{H}),E(\mathscr{H}))$ where $V(\mathscr{H})$ is a set of elements called vertices, and $E(\mathscr{H})$ is a family of subsets of $V(\mathscr{H})$ called hyperedges (or simply edges). Hypergraphs are known as graphs when their edges are of size precisely two. A transversal in a hypergraph $\mathscr{H}$ is a set $T\subseteq V(\mathscr{H})$ which intersects every edge of $\mathscr{H}$. It is called minimal if it is inclusion-wise minimal, i.e., if none of its proper subsets is a transversal. The problem of enumerating the minimal transversals of a hypergraph, usually denoted by Trans-Enum, is one of the most important problems in algorithmic enumeration, for it has far-reaching implications in various areas of computer science such as logic, database theory, data profiling, or artificial intelligence [37, 16, 30, 5]; we refer the reader to [16] and the surveys [18, 22] for a comprehensive overview on the fundamental and practical aspects of this problem.

In a typical enumeration problem such as Trans-Enum, a first observation to be made is that the number of solutions can be exponential in both $n$, the number of vertices, and $m$, the number of edges. Thus, asking for running times which are polynomial in $n+m$ is meaningless. Rather, we are interested in algorithms performing in output-polynomial time, i.e., that run in a time which is polynomial in both the input size, and the output size. More strict notions of tractability can be required, such as incremental-polynomial times, and polynomial delay. We say that an algorithm runs in incremental-polynomial time if it produces the $i^{\text{th}}$ solution in a time which is polynomial in the input size plus $i$. An algorithm is said to run with polynomial delay if the times before the first output, after the last output, and in between two consecutive outputs are bounded by a polynomial in the input size only. To date, the best-known algorithm solving Trans-Enum is due to Fredman and Khachiyan [21] and runs in quasi-polynomial incremental time. Since then, output-polynomial time algorithms were obtained for several important classes, including those generalizing that of bounded degree [17], or bounded edge size [38].

Dominating sets are among the most studied objects in graphs. A dominating set in a graph $G$ is a set $D\subseteq V(G)$ such that every vertex is either in $D$, or adjacent to a vertex of $D$. Again, it is called minimal if it is inclusion-wise minimal. The problem of enumerating minimal dominating sets in graphs is denoted by Dom-Enum. Note that being a dominating set of $G$ can be rephrased as being a transversal of each closed neighborhood of $G$, so, Dom-Enum is a special case of Trans-Enum with a linear number of hyperedges.

The problem Dom-Enum has gained lots of interest since it has been shown, perhaps surprisingly, to be polynomially equivalent to Trans-Enum, even when restricted to cobipartite graphs [33]. In particular, this work has initiated a fruitful line of research of characterizing which graph classes admit output-polynomial algorithms, in the hope of better understanding the underlying structure that makes Trans-Enum tractable. For example, polynomial-delay algorithms were obtained for various graph classes including chordal graphs [34] (with linear delay on some subclasses [33, 13]), graphs of bounded degeneracy [17], line graphs [35], graphs of bounded clique-width [11], or graph classes related to permutation graphs and their generalizations [32, 23, 8]. Incremental-polynomial time algorithms were obtained for graphs of bounded conformality [38], $C_{\le 6}$-free graphs [27], chordal bipartite graphs [24], $(C_4,C_5,\text{claw})$-free graphs [32], or graphs arising in geometrical contexts [20, 23] including unit-disk and unit-square graphs. Output-polynomial time algorithms are known for $\log n$-degenerate graphs [17], and graphs of bounded clique number [7].

In [33], the authors also include two natural variants of domination in their study: total and connected dominating sets. A total dominating set is a set $D$ such that every vertex of $G$ has a neighbor in $D$. In other words, elements of $D$ cannot “dominate” themselves and need a neighbor in the set. A connected dominating set is a dominating set that induces a connected subgraph. Note that any connected dominating set is a total dominating set, as long as it has more than one element, making the intersection of these two notions irrelevant to study. Perhaps not surprisingly, the authors in [33] show that the problems of enumerating minimal total and connected dominating sets, denoted TDom-Enum and CDom-Enum, respectively, are equivalent to Trans-Enum when restricted to split graphs. These equivalences on a relatively restricted graph class suggest that these variants of Dom-Enum are challenging, and may explain why they have received less attention in the literature.

Regarding total dominating sets, a first observation is that they are transversals of open neighborhoods. This implies an incremental quasi-polynomial time algorithm for the problem using the results of Fredman and Khachiyan [21]. However, few output-polynomial time algorithms are known for specific instances of TDom-Enum. Among them, we cite the class of chordal bipartite graphs, which admits a polynomial-delay algorithm for the problem [24].

Concerning connected dominating sets, it is not known whether the problem reduces to Trans-Enum. It has in fact been conjectured that this is not the case in [6]. Rather, it has been shown in [33] that the problem reduces to the enumeration of minimal transversals of an implicit hypergraph given by the minimal separators of the graph. However, the number of such separators may be exponential, and are intractable to compute [9]. The only work known to us dealing with connected dominating sets enumeration, apart from [33], falls under the input-sensitive approach [25, 26, 1] where one aims at small exponential times. Still, we note that some essential questions concerning output-sensitive enumeration were addressed in [1] such as the $\mathrm{𝖭𝖯}$-hardness of the associated extension problem, i.e., deciding if a given set $U\subseteq V(G)$ is contained in some minimal connected dominating set.

Note that, in the literature, particular attention has been put into characterizing the status of these problems on bipartite, split, and cobipartite graphs. This is because such instances contain the incidence graph of any hypergraph, which is fundamentally challenging and makes interesting links with Trans-Enum. However, and in contrast to the split and cobipartite cases, the case of bipartite graphs has been particularly challenging with the question of the (in)tractability of these problems raised in various works [36, 24]. Only recently has an output-polynomial time algorithm been provided for Dom-Enum in a generalization of bipartite graphs [7]. Still the problem is not known to admit a polynomial-delay algorithm. Concerning TDom-Enum and CDom-Enum, it is also open, to the best of our knowledge, whether they can be solved with polynomial delay, or even in output-polynomial time, in bipartite graphs. Among natural subclasses of bipartite graphs, the case of chordal bipartite graphs has been studied as it admits nice structural properties analogous to chordal graphs, such as perfect elimination orderings and linearly many minimal separators. We note, however, that even in this particular class, the existence of a polynomial-delay algorithm for Dom-Enum seems open, and has been left open in [24].

The following two natural questions arise from the literature.

Only the case of minimal total dominating sets has been settled for chordal bipartite graphs, with the following result.

We assume familiarity with standard terminology from graph and hypergraph theory, and refer to [15, 3] for notations not included below.

We describe the sequential method. As by Propositions 2–4, the problems Dom-Enum, TDom-Enum, and CDom-Enum can be seen as particular instances of Trans-Enum we choose to follow the presentation of [2], and refer the reader to [17, 19, 7] for more details on this approach.

Let $\mathscr{H}\subseteq 2^V$ be a hypergraph on vertex set $V=\{v_1,\mathrm{\dots },v_n\}$. For $1\le i\le n$ we denote by $V_i:=\{v_1,\mathrm{\dots },v_i\}$ the set of its first $i$ vertices, by ${\mathscr{H}}_i:=\mathscr{H}[V_i]$ the hypergraph induced by $V_i$, and set $V_0:={\mathscr{H}}_0:=Tr({\mathscr{H}}_0):=\mathrm{\varnothing }$. In addition, for $S\subseteq V_i$ and $v\in S$, we note ${\mathrm{𝗉𝗋𝗂𝗏}}_i(S,v)$ the set of private edges of $v$ with respect to $S$ in ${\mathscr{H}}_i$. Given a minimal transversal $T\in Tr({\mathscr{H}}_{i+1})$ for , we denote by $\mathrm{𝗉𝖺𝗋𝖾𝗇𝗍}(T,i+1)$ the parent of $T$ with respect to $i+1$ obtained after repeatedly removing from $T$ the vertex of smallest index $v$ such that ${\mathrm{𝗉𝗋𝗂𝗏}}_i(T,v)=\mathrm{\varnothing }$. By definition, every $T$ has a unique parent. Lastly, we denote by $\mathrm{𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇}(T^{\star },i)$, for $T^{\star }\in Tr({\mathscr{H}}_i)$, the family of $T\in Tr({\mathscr{H}}_{i+1})$ such that $T^{\star }=\mathrm{𝗉𝖺𝗋𝖾𝗇𝗍}(T,i+1)$.

The next two lemmas are central to the description of the algorithm: they define a tree structure where nodes are pairs $(T,i)$ with $T\in Tr({\mathscr{H}}_i)$ and that will be traversed in a DFS manner in order to produce every leaf $T\in Tr(\mathscr{H})=Tr({\mathscr{H}}_n)$ as a solution. We refer to [2] for the proofs of these statements, which follow from the definition of the $\mathrm{𝗉𝖺𝗋𝖾𝗇𝗍}$ relation.

Finally, the whole framework culminates in the following statement that reduces Trans-Enum to the enumeration of the children of a given pair $(T,i)$ with $T\in Tr({\mathscr{H}}_i)$, , while preserving polynomial delay and space.

In the following, given $T^{\star }$ and $i$ as above, let

be the family of hyperedges of ${\mathscr{H}}_{i+1}$ that are not hit by $T^{\star }$. The following shows that children may be found by considering minimal extensions to ${\mathscr{H}}_{i+1}$ of minimal transversals of ${\mathscr{H}}_i$.

In this section, we apply the sequential method to Trans-Enum restricted to hypergraphs of closed neighborhoods of chordal bipartite graphs to show that Question 1 admits a positive answer. More specifically, we use the weak-simplicial elimination ordering of chordal bipartite graphs to restrict the instance of minimal extensions enumeration to a variant of domination in bipartite chain graphs, which is tractable. By Corollary 14, this allows us to obtain Theorem 18.

In the following, let $G$ be a chordal bipartite graph on $n$ vertices and $v_1,\mathrm{\dots },v_n$ be a weak-simplicial ordering of its vertices as provided by Proposition 5. Let $\mathscr{H}$ be its hypergraph of closed neighborhoods, $i\in \{1,\mathrm{\dots },n-1\}$ be an integer and $T$ be a minimal transversal of ${\mathscr{H}}_i$ as in the statement of Corollary 14. We will show how to enumerate the minimal transversals of ${\mathrm{\Delta }}_{i+1}$ in polynomial time and space, to derive the desired result.

First note that since the edges of ${\mathrm{\Delta }}_{i+1}$ belong to ${\mathscr{H}}_{i+1}$ and are incident to $v_{i+1}$, they may be equal to $N[v_{i+1}]$ if $N[v_{i+1}]\subseteq V_{i+1}$, or to $N[u]$ for some neighbor $u$ of $v_{i+1}$ if $N[u]\subseteq V_{i+1}$. Note that in the later case, the set $N[u]$ may contain vertices at distance 2 from $v_{i+1}$. From now on, let $B$ be the set of vertices $u\in N(v_{i+1})$ such that $N[u]\in {\mathrm{\Delta }}_{i+1}$, and let

be the remaining vertices that lie in some edge of ${\mathrm{\Delta }}_{i+1}$. Consequently $B\subseteq N(v_{i+1})$ and $R\subseteq N(v_{i+1})\cup N^2(v_{i+1})$. Thus the graph $H=G_i[R\cup B]$ is an induced subgraph of $G_i[N(v_{i+1})\cup N^2(v_{i+1})]$ which, by Proposition 5, is a bipartite chain. Hence $H$ is a bipartite chain. We denote by $(X,Y)$ the bipartition of $H$ where $B\subseteq X\subseteq N(v_{i+1})$, and by $x_1,\mathrm{\dots },x_p$ and $y_1,\mathrm{\dots },y_q$ the respective orderings of $X$ and $Y$ satisfying $N(x_j)\cap Y\subseteq N(x_{\mathrm{\ell }})\cap Y$ and $N(y_{\mathrm{\ell }})\cap X\subseteq N(y_j)\cap X$ for all ; see Section 2 and Figure 1 for an illustration of the situation.

In what remains we shall call blue the vertices in $B$, red those in $R$, and characterize minimal transversals of ${\mathrm{\Delta }}_{i+1}$ as particular sets analogous to red-blue dominating sets where red and blue vertices may be selected in order to dominate blue vertices.

Recall that CDom-Enum amounts to list the minimal transversals of the (implicit) hypergraph of minimal separators of a given graph $G$, i.e., Proposition 4. By Proposition 7, this hypergraph can be constructed in polynomial time if $G$ is chordal bipartite. In this section, we moreover show that this hypergraph has bounded conformality in that case. As a corollary, we can use the algorithm of Khachiyan et al. in [38] to list minimal connected dominating sets in incremental-polynomial time in chordal bipartite graphs, providing a positive answer to Question 2.

Let us define the notion of conformality introduced by Berge in [3]. We say that a hypergraph $\mathscr{H}$ is of conformality $c$ if the following property holds for every subset $X\subseteq V(\mathscr{H})$: $X$ is contained (as a subset) in a hyperedge of $\mathscr{H}$ whenever each subset of $X$ of cardinality at most $c$ is contained (as a subset) in a hyperedge of $\mathscr{H}$. See also [3, 38] for other equivalent characterizations of bounded conformality. We recall that a hypergraph $\mathscr{H}$ is called Sperner if $E_1⊈E_2$ for any two distinct hyperedges $E_1,E_2$ in $\mathscr{H}$.

Khachiyan, Boros, Elbassioni, and Gurvich proved the following.

Using the properties of minimal separators of chordal bipartite graphs given in Section 2, we obtain the following, whose proof is moved to appendix, and derive the desired algorithm as a corollary of Theorem 19 and Lemma 20.

It is already known that the sequential method may not directly provide output-polynomial time algorithms for Trans-Enum in general; see e.g. [2] for explicit statements. We adapt the construction in [2] to show that this still holds for hypergraphs of (open or closed) neighborhoods of bipartite graphs, i.e., that we may not expect to get tractable algorithms for TDom-Enum and Dom-Enum using this technique.

We begin with Dom-Enum and later detail the modifications to be performed for the statement to hold for TDom-Enum. In the following by $𝒩(G)$ we mean the hypergraph of closed neighborhoods of $G$, whose minimal transversals are precisely the minimal dominating sets of $G$; see Section 2.

Recall that in Multicolored Independent Set problem, we are given a graph $G$, an integer $k$, and a partition $𝒱=(V_1,V_2,\mathrm{\dots },V_k)$ of $V(G)$ such that $V_i$ is an independent set for every $1\le i\le k$. Sets $V_1,\mathrm{\dots },V_k$ are usually referred to as color classes. The goal is then to decide whether there exists an independent set in $G$ containing precisely one vertex from each $V_i$, i.e., that is multicolored. See [12] for more details on this problem.

Due to space constraints, we omit the formal description of the reduction and only include the statement we derive. We refer the reader to Figure 2 for an idea of the construction, and to the appendix for its formal description and proof. The idea is to show that a minimal transversal $T^{\star }$ of $\mathscr{H}$ induced by all but two of its vertices can be extended into a non-trivial child if and only if an instance $G$ of multicolored independent set admits a solution.

A consequence of Lemma 22 is that the sequential approach may not be directly applied to solve Dom-Enum, even in bipartite graphs. Moreover, in our construction, no vertex $v$ of $T^{\star }$ is made self-private, i.e., no $v$ has its closed neighborhood as a private edge. Furthermore, the elements in the color classes are dominated by $T^{\star }$, and their role is thus limited to dominate the $c_i$’s in an extension. Hence, by keeping the same construction, all the arguments of the proof hold for the hypergraph of open neighborhoods of $G$. We derive that the sequential approach may not be directly be used for TDom-Enum neither.

Our final result is a proof that Trans-Enum reduces to CDom-Enum on bipartite graphs, which we are not aware of being previously known or directly implied by other results. In fact, by Proposition 4, if we can construct a graph where (almost) every minimal separator is in a one to one correspondence to our hyperedges, we are done.

Let $\mathscr{H}$ be the input hypergraph to Trans-Enum with $E(\mathscr{H})=\{E_1,\mathrm{\dots },E_m\}$ and $V(\mathscr{H})=\{u_1,\mathrm{\dots },u_n\}$ and assume w.l.o.g. that $\mathscr{H}$ is a Sperner hypergraph. To obtain $G$, the input to CDom-Enum, we start with the incidence bipartite graph of $\mathscr{H}$, that is, $\{v_1,\mathrm{\dots },v_n\}$, $\{e_1,\mathrm{\dots },e_m\}\subset V(G)$, where $v_i$ corresponds to $u_i\in V(\mathscr{H})$ and $e_j$ corresponds to $E_j\in E(\mathscr{H})$, and $v_i{e}_j\in E(G)$ if and only if $u_i\in E_j$. To conclude the construction of $G$, we add two vertices $v^{\prime }$ and $v^{\star }$, the edge $v^{\prime }{v}^{\star }$, and the edges $v^{\star }{v}_i$ for all $1\le i\le n$. Due to space constraints the proofs of the following are omitted as well.

In this paper, we investigated the complexity of Dom-Enum and its two variants TDom-Enum and CDom-Enum in chordal bipartite graphs. We obtained polynomial-delay algorithms for the first two problems, and an incremental-polynomial time algorithm for the last problem. Then we gave evidence that the techniques used for Dom-Enum and TDom-Enum may not be pushed directly to bipartite graphs. As of CDom-Enum, we proved a stronger statement that CDom-Enum is as hard as Trans-Enum in bipartite graphs, with the later problem being open since more than forty years [16].

We leave open the existence of polynomial-delay algorithms for Dom-Enum and TDom-Enum in bipartite graphs, and for CDom-Enum in chordal bipartite graphs. Concerning this last case, we note that obtaining polynomial delay is open for Trans-Enum on hypergraph of bounded dimension, which define a proper subclass of hypergraphs of bounded conformality. Hence, in order to improve Theorem 21, one either has to find another strategy, or should aim at improving the results in [16, 38] first.