# Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets

Marthe Bonamy, Oscar Defrain, Piotr Micek, Lhouari Nourine

<figure><img src="image_1.png" /></figure>

► To cite this version:

Marthe Bonamy, Oscar Defrain, Piotr Micek, Lhouari Nourine. Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets. Discrete Mathematics, 2020, 349 (4), pp.114904. 10.1016/j.disc.2025.114904. hal-05534629

HAL Id: hal-05534629

https://hal.science/hal-05534629v1

Submitted on 3 Mar 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets*

Marthe Bonamy¹, Oscar Defrain²,
Piotr Micek³, and Lhouari Nourine⁴

¹CNRS, LaBRI, Université de Bordeaux, France.

²LIS, Aix-Marseille Université

⁴LIMOS, Université Clermont Auvergne, France.

³Theoretical Computer Science Department,
Faculty of Mathematics and Computer Science,
Jagiellonian University, Kraków, Poland.

April 5, 2020

## Abstract

Enumerating minimal transversals in a hypergraph is a notoriously hard problem. It can be reduced to enumerating minimal dominating sets in a graph, in fact even to enumerating minimal dominating sets in an incomparability graph. We provide an output-polynomial time algorithm for incomparability graphs whose underlying posets have bounded dimension. Through a different proof technique, we also provide an output-polynomial time algorithm for their complements, i.e., for comparability graphs of bounded dimension posets. Our algorithm for incomparability graphs relies on the geometrical representation of incomparability graphs with bounded dimension, as given by Golumbic et al. in 1983. It runs with polynomial delay and only needs polynomial space. Our algorithm for comparability graphs is based on the flipping method introduced by Golovach et al. in 2015. It performs in incremental-polynomial time and possibly requires exponential space.

**Keywords:** minimal dominating sets, poset dimension, comparability graphs, incomparability graphs, algorithmic enumeration

## 1 Introduction

The problem we consider in this paper is the enumeration of all (inclusion-wise) minimal dominating sets of a graph, denoted by DOM-ENUM. A dominating set in a graph $G$ is a set of vertices $D$ such that every vertex of $G$ is either in $D$, or is adjacent to a vertex in $D$. It is (inclusion-wise) minimal if no strict subset of $D$ is a dominating set. Due to its equivalence with the

<footnote>*The first author has been supported by the ANR project GrR ANR-18-CE40-0032 (2019-2023). The second and last authors have been supported by the ANR project GraphEn ANR-15-CE40-0009. The third author has been supported by the Polish National Science Center grant (BEETHOVEN; UMO-2018/31/G/ST1/03718).</footnote>
problem of enumerating all (inclusion-wise) minimal transversals of a hypergraph, denoted by TRANS-ENUM, DOM-ENUM has been widely studied this last decade. Latest publications on the problem include [GHK$^{+}$18, KKP18, BDHR19, DN19, GKLS19].

As an $n$-vertex graph $G$ may contain a number $|\mathcal{D}(G)|$ of minimal dominating sets which is exponential in $n$, one can only aim to provide algorithms running in time exponential in $n$, or, to provide algorithms whose running time is polynomial in $n + |\mathcal{D}(G)|$. We only focus here on algorithms of the second type, and refer to [FGPS08, CHvHK13, GKLS19] for input exponential-time algorithms for the problem we consider in this paper. An algorithm of the second type—running in polynomial time in the sizes of both the input and the output—is called *output-polynomial*. It is said to be running in *incremental-polynomial time* if it moreover outputs the $i$-th solution in a time which is bounded by a polynomial in $n$ plus $i$, for all $i$. If the running times before the first output, between any two consecutive outputs, and after the last output, are bounded by a polynomial in $n$ only, then the algorithm is said to be running with *polynomial delay*. We refer the reader to [JYP88, CKP$^{+}$19, Str19] for a more detailed introduction on the complexity of enumeration algorithms.

The existence of an output-polynomial time algorithm for DOM-ENUM (or TRANS-ENUM) is a long-standing open question [EG95, EMG08, KLMN14]. To date, the best known algorithm is due to Fredman and Khachiyan and comes from the dualization of monotone Boolean functions [FK96]. It runs in output quasi-polynomial time $N^{o(\log N)}$ where $N = n + |\mathcal{D}(G)|$. Output-polynomial time algorithms are known for several classes of graphs, including $\log(n)$-degenerate graphs [EGM03] and triangle-free graphs [BDHR19], later extended to $K_t$-free, paw-free, and diamond-free graphs in [BDH$^{+}$20]. Incremental-polynomial time algorithms are known for chordal bipartite graphs [GHK$^{+}$16], $\{C_6, C_8\}$-free bipartite graphs [KKP18], graphs of bounded conformality [BEGK04], and unit square graphs [GHK$^{+}$18]. Polynomial-delay algorithms are known for bounded degeneracy graphs [EGM03], for chordal, and line graphs [KLM$^{+}$15a, KLM$^{+}$15b]. Finally, linear-delay algorithms are known for graphs of bounded cliquewidth [Cou09], permutation and interval graphs [KLM$^{+}$13], split and $P_7$-free chordal graphs [KLMN14, DN19]. In terms of negative results, DOM-ENUM is as hard in co-bipartite graphs as in general [KLMN14].

The graph classes we consider in the following are related to partially ordered sets, in short posets. If $P$ is a poset on the set of elements $V$, then the *comparability graph* of $P$ is the graph $G$ defined on vertex set $V(G) = V$ and where two distinct vertices $u$ and $v$ are adjacent if they are comparable in $P$. The *incomparability graph* of $P$ is the complement: $u$ and $v$ are adjacent if they are incomparable in $P$. Note that every bipartite graph is a comparability graph, hence every co-bipartite graph is an incomparability graph. The dimension, introduced in 1941 by Dushnik and Miller [DM41], is a key measure of complexity of posets and an analogue of the chromatic number for graphs. The *dimension* of a poset $P$ is the least integer $d$ such that elements of $P$ can be embedded into $\mathbb{R}^d$ in such a way that $x \le y$ in $P$ if and only if the point of $x$ is below the point of $y$ with respect to the product order of $\mathbb{R}^d$ (the component-wise comparison of coordinates). Alternatively, the dimension of a poset can be defined as the least integer $d$ such that $P$ is the intersection of $d$ linear orders $\le_1, \dots, \le_d$ on same ground set, i.e., $x \le y$ in $P$ if and only if $x \le_1 y, \dots, x \le_d y$.

Since DOM-ENUM is as hard in incomparability graphs as in general, an output-polynomial algorithm would be a major, albeit unlikely, breakthrough. Algorithms for natural subclasses of incomparability graphs, such as interval graphs (incomparability graphs of interval orders) and permutations graphs (incomparability graphs of 2-dimensional posets), were obtained in [KLM$^{+}$13]. Our contribution is as follows.
**Theorem 1.1.** For any fixed integer $d$, there is a polynomial delay and space algorithm enumerating minimal dominating sets in the incomparability graphs of posets of dimension at most $d$, represented as the intersection of $d$ linear orders.

It should be noted here that the incomparability graphs of posets of dimension $d$ are $d$-trapezoid graphs, for which minimal dominating sets enumeration was already shown to be possible with linear delay after $n^{O(1)}$-time preprocessing, when given with their representation [GHK$^{+18}$]. We nevertheless point that our algorithm is remarkably simpler than the one obtained in [GHK$^{+18}$] which may be of practical interest for implementations purposes. Our algorithm relies on the geometrical representation of incomparability graphs of bounded dimension, which was given by Golumbic et al. in [GRU83].

DOM-ENUM in comparability graphs is also widely open: only the subcase of bipartite graphs (comparability graphs of posets of height at most 2) has been solved recently [BDHR19]. However, there is no reason to believe that DOM-ENUM is as hard for comparability graphs as in general. We prove that it is tractable when the underlying poset has bounded dimension, as follows.

**Theorem 1.2.** For any fixed integer $d$, there is an incremental-polynomial time algorithm enumerating minimal dominating sets in the comparability graphs of posets of dimension at most $d$.

The algorithm for comparability graphs is based on the *flipping method* recently introduced by Golovach et al. in [GHKV15]. It uses as a blackbox the algorithm of Khachiyan et al. in [KBEG07] for the dualization in hypergraphs of bounded conformality and therefore may need space that is exponential in the size of the input. It also covers the comparability graphs of $S_t$-free posets.

In addition to these contributions, we show with Lemma 3.3 how the flipping method can be improved to work only using polynomial space. While this is not enough to make Theorem 1.2 run in polynomial space, it turns existing algorithms for line graphs [GHKV15], graphs of girth at least 7, chordal bipartite graphs [GHK$^{+16}$], and unit-square graphs [GHK$^{+18}$], into incremental polynomial time algorithms using polynomial space.

The paper is organized as follows. In Section 2 we introduce definitions and notation from graph and order theory that will be used throughout the paper. In Section 3, we recall the flipping method from [GHKV15] and show how it can be improved to run using polynomial space. We then show in Section 4 how the method can be reduced to red-blue domination—a variant of domination—in comparability graphs. In Section 5, we show how red-blue domination can be solved in the comparability graphs of posets of bounded dimension, and conclude with our first algorithm. The algorithm for incomparability graphs is presented in Section 6. We conclude the paper with discussions and open problems in Section 7.

# 2 Preliminaries

The objects considered in this paper are finite. If $A$ and $B$ are sets, we denote by $2^A$ the set of all subsets of $A$, and by $A \times B$ the Cartesian product $\{(a, b) | a \in A, b \in B\}$.

We start with some basic notions from graph theory. A graph $G$ is a pair $(V(G), E(G))$ with $V(G)$ its set of vertices (or *ground set*) and $E(G) \subseteq \{\{u, v\} | u, v \in V(G), u \neq v\}$ its set of edges. Edges are denoted by $uv$ (or $vu$) instead of $\{u, v\}$. Two vertices $u, v$ of $G$ are called *adjacent* if $uv \in E(G)$. A *clique* (respectively an *independent set*) in a graph $G$ is a set of pairwise adjacent (respectively non-adjacent) vertices. A *biclique* is a set of vertices that can be partitioned into two independent sets $A, B$ such that every vertex in $A$ is adjacent to every
vertex in B. We denote $K_t$ to be the clique on $t$ elements, and $K_{t,t}$ to be the biclique on $2t$ elements of partition A, B such that $|A| = |B| = t$. The subgraph of G induced by $X \subseteq V(G)$, denoted by $G[X]$, is the graph $(X, E(G) \cap \{{\{u, v\} \mid u, v \in X, u \neq v\}})$; $G - X$ is the graph $G[V(G) \setminus X]$. For every graph $H$, we say that $G$ is *H-free* if no induced subgraph of $G$ is isomorphic to $H$.

**Domination** Let $G$ be a graph and $u$ be a vertex of $G$. The neighborhood of $u$ is the set $N(u) = \{v \in V(G) \mid uv \in E(G)\}$. The closed neighborhood of $u$ is the set $N[u] = N(u) \cup \{u\}$. For a subset $X \subseteq V(G)$ we define $N[X] = \bigcup_{x \in X} N[x]$ and $N(X) = N[X] \setminus X$. Let $D, X \subseteq V(G)$ be two subsets of vertices of $G$. We say that $D$ dominates $X$ if $X \subseteq N[D]$. It is (inclusion-wise) minimal if $X \not\subseteq N[D \setminus \{x\}]$ for any $x \in D$. A (minimal) dominating set of $G$ is a (minimal) dominating set of $V(G)$. The set of all minimal dominating sets of $G$ is denoted by $\mathcal{D}(G)$. The problem of enumerating $\mathcal{D}(G)$ given $G$ by Dom-ENUM. For a graph $G$, we denote by MIS($G$) the set of all its (inclusion-wise) maximal independent sets, and by MIS-ENUM the problem of generating MIS($G$) from $G$. It is easily observed that every maximal independent set is a minimal dominating set, hence that MIS($G$) $\subseteq \mathcal{D}(G)$. However, MIS-ENUM appears to be much more tractable than Dom-ENUM, as witnessed by the many efficient algorithms that are known for the problem [TIAS77, JYP88, MU04]. These last two observations are the starting point of the flipping method introduced in [GHKV15] which we describe at Section 3.

Let $u \in D$. A vertex $v$ that is adjacent only to $u$ in $D$, i.e., for which $N[v] \cap D = \{u\}$, is a *private neighbor* of $u$ with respect to $D$. Note that $u$ can be its own private neighbor (we say that $u$ is *self-private*). The set of private neighbors of $u \in D$ is denoted by $\text{Priv}(D, u)$. A set $I \subseteq V(G)$ is called *irredundant* if $\text{Priv}(I, x) \neq \emptyset$ for all $x \in I$. Then $D$ is a minimal dominating set of $G$ if and only if it is both a dominating set, and an irredundant set.

A graph $G$ together with two disjoint subsets $R, B \subseteq V(G)$ constitutes a *red-blue graph* $G(R, B)$, where we consider vertices in $R$ to be *red* and those in $B$ to be *blue*. We do not require for $R$ and $B$ to partition $V(G)$. A *red dominating set* of $G(R, B)$ is a red set $D \subseteq R$ that dominates $B$, i.e., that is such that $B \subseteq N[D]$. It is (inclusion-wise) minimal if $B \not\subseteq N[D \setminus \{x\}]$ for any $x \in D$. We denote $\mathcal{D}_G(R, B)$ to be the set of all minimal red dominating sets of $G(R, B)$, and *RED-BLUE-DOM-ENUM* the problem of enumerating $\mathcal{D}_G(R, B)$ given $G, R$, and $B$. The index may be dropped when the graph $G$ is clear from the context. In the context of red-blue domination, we implicitly restrict our attention to the dominating sets that contain only red vertices, and to private neighbors that are blue.

**Posets** A *partially ordered set* (or *poset*) $P = (V, \leqslant)$ is a pair where $V$ is a set and $\leqslant$ is a binary relation on $V$ that is reflexive, anti-symmetric and transitive. Two elements $u$ and $v$ of $P$ are said to be *comparable* if $u \leqslant v$ or $v \leqslant u$, otherwise they are said to be *incomparable*, denoted $u \parallel v$. A *chain* in a poset $P$ is a set of pairwise comparable elements in $P$. An *antichain* in a poset $P$ is a set of pairwise incomparable elements in $P$. A poset $P$ is called a *total order* (or *linear order*) if $V$ is a chain. Posets are represented by their Hasse diagram; see Figure 1.

The *comparability graph* of a poset $P = (V, \leqslant)$ is the graph $G$ defined on same ground set $V(G) = V$ and where two vertices $u$ and $v$ are made adjacent if they are comparable in $P$. The *incomparability graph* (or *co-comparability graph*) of $P$ is the complement: $u$ and $v$ are made adjacent if they are incomparable in $P$, see Figure 1.

We now define notations from order theory that will be used in the context of a poset and its *comparability graph* only. Let $G$ be the comparability graph of a poset $P = (V, \leqslant)$. The *ideal of* $u$ is the set $\downarrow u = \{v \in V \mid v \leqslant u\}$, and the *filter of* $u$ is the dual $\uparrow u = \{v \in V \mid u \leqslant v\}$. Note that $N[u] = \downarrow u \cup \uparrow u$. These notions extend to subsets $S \subseteq V$ as follows: $\downarrow S = \bigcup_{u \in S} \downarrow u$,
<figure><img src="image_3.png" /><figcaption>Figure 1: The Hasse diagram of a poset (left), its comparability graph (middle), and incompa-
rability graph (right).</figcaption></figure>

↑S = ⋃ u∈S ↑u. We note Min(S) and Max(S) the sets of minimal and maximal elements in S
with respect to ≤. Clearly, Min(S) and Max(S) define antichains of P for every S ⊆ V. In this
context, a (minimal) dominating set of G is a (minimal) set D ⊆ V such that ↑D ∪ ↓D = V,
and a (maximal) independent set of G is a (maximal) antichain of P.

The *dimension* of a poset *P* = (*V*, *≤*) is the least integer *d* such that *P* is the intersection of *d* linear orders *≤*₁, ..., *≤*<sub>*d*</sub> on *V*, i.e., *x* ≤ *y* if and only if *x* ≤*₁* *y*, ..., *x* ≤*<sub>*d*</sub>* *y*.

We call the poset induced by $X \subseteq V$, denoted $P[X]$, the suborder restricted on the elements of $X$ only. A poset $P = (V, \leq)$ is *bipartite* if $V$ can be partitioned into two sets $A, B$ such that $a < b$ implies $a \in A$ and $b \in B$. We denote by $S_t$ and call *standard example of order t* the poset with bipartition $A = \{a_1, \dots, a_t\}$ and $B = \{b_1, \dots, b_t\}$ such that $a_i < b_j$ for all $i \neq j \in \{1, \dots, t\}$. See Figure 2 for an example. It is well known that $S_t$ has dimension $t$ [DM41]. Note that dimension is monotone under taking induced suborders. Therefore, posets containing a large standard example as a suborder have large dimension. The converse is however not true, as there are posets of unbounded dimension with no $S_2$ as an induced suborder, see [Tro92] for a comprehensive study and references.

<figure><img src="image_4.png" /><figcaption>Figure 2: The standard example of order four.</figcaption></figure>

**Hypergraphs** A hypergraph $\mathcal{H}$ is a pair $(V(\mathcal{H}), \mathcal{E}(\mathcal{H}))$ with $V(\mathcal{H})$ its set of vertices (or ground set) and $\mathcal{E}(\mathcal{H}) \subseteq 2^{V(\mathcal{H})}$ its set of edges (or hyperedges). A hypergraph $\mathcal{H}$ is called *Sperner* if $E_1 \not\subseteq E_2$ for any two distinct hyperedges in $\mathcal{H}$. A *transversal* of $\mathcal{H}$ is a set $T \subseteq V(\mathcal{H})$ that intersects every hyperedge in $\mathcal{H}$. It is (inclusion-wise) minimal if $T \setminus \{x\}$ is not a transversal of $\mathcal{H}$ for any $x \in T$. The sets of all minimal transversals of $\mathcal{H}$ is denoted by $\text{Tr}(\mathcal{H})$, and the problem of enumerating $\text{Tr}(\mathcal{H})$ given $\mathcal{H}$ by **TRANS-ENUM**.

Note that `DOM-ENUM` appears as a particular case of `TRANS-ENUM` when considering the hypergraph `N(G)` of closed neighborhoods of a given graph `G`, defined by `V(N(G)) = V(G)` and `E(N(G)) = {N[x] | x ∈ V(G)}`. Indeed, a minimal dominating set of `G` is a minimal set intersecting every neighborhood of `G`, and hence `Tr(N(G)) = D(G)`. In fact, the two problems were shown polynomially equivalent<fnref n="1" /> by Kanté et al. in [KLMN14] even when restricted to co-

<footnote n="1">¹Two enumeration problems $\Pi_A$ and $\Pi_B$ are said to be *polynomially equivalent* when there is an output-polynomial time algorithm solving $\Pi_A$ if and only if there is one solving $\Pi_B$. If there is an output-polynomial time algorithm solving $\Pi_A$ whenever there is one solving $\Pi_B$, then we say that $\Pi_B$ is *(at least) as hard as* $\Pi_A$.</footnote>
bipartite graphs. This in particular shows that `DOM-ENUM` in co-bipartite graphs is as hard as for general graphs. As for `TRANS-ENUM` and `RED-BLUE-DOM-ENUM`, it is easily seen that they are polynomially equivalent even when restricted to red-blue bipartite graphs of bipartition red and blue. First, every red-blue graph $G(R, B)$ corresponds to a hypergraph $\mathcal{H}$, defined by $V(\mathcal{H}) = R$ and $\mathcal{E}(\mathcal{H}) = \{N(x) \cap R \mid x \in B\}$, satisfying $\text{Tr}(\mathcal{H}) = \mathcal{D}(R, B)$. Then, every instance $\mathcal{H}$ of `TRANS-ENUM` corresponds to a bipartite instance $G(R, B)$ of `RED-BLUE-DOM-ENUM`, defined by $R = V(\mathcal{H})$, $B = \{y_E \mid E \in \mathcal{E}(\mathcal{H})\}$, with an edge $xy_E$ if and only if $x \in E$, which satisfies $\mathcal{D}(R, B) = \text{Tr}(\mathcal{H})$.

# 3 Polynomial-space flipping method

Golovach, Heggernes, Kratsch and Villanger introduced in [GHKV15] the so-called *flipping method* to efficiently enumerate minimal dominating sets in line graphs. This method was later used with much success [GHK$^{+}$16, GHK$^{+}$18, KKP18]. A key step in this method is the *flipping operation*. We recall it below and in the process, we show how the flipping method can be made to run with polynomial space (in contrast to exponential space from the original version).

## 3.1 The flipping operation

Let $G$ be an $n$-vertex graph and $v_1, \dots, v_n$ be any ordering of vertices in $G$. We note that this order induces a lexicographical order on the family $2^{V(G)}$. Let $D$ be a minimal dominating set of $G$ such that $G[D]$ contains at least one edge incident to some vertex $u$. The following procedure is illustrated in Figure 3. Since $D$ is a minimal dominating set, the set $\text{Priv}(D, u)$ is not empty. Let $v \in \text{Priv}(D, u)$. Since $u$ is adjacent with another vertex from $D$, we have $u \notin \text{Priv}(D, u)$, so $v \neq u$. We want to replace $u$ with $v$ (*flip* $u, v$) and obtain another minimal dominating set. Let $X_{uv} \subseteq \text{Priv}(D, u) \setminus N[v]$ be the lexicographically smallest maximal independent set in $G[\text{Priv}(D, u) \setminus N[v]]$. Note that $X_{uv}$ is obtained from the empty set by iteratively adding a vertex of smallest index in $\text{Priv}(D, u) \setminus \{v\} \cup X_{uv}$, until no such vertex exists. Consider the set $D' = (D \setminus \{u\}) \cup X_{uv} \cup \{v\}$. Note that $D'$ is a (not necessarily minimal) dominating set of $G$. Some vertices of $D'$ may have no private neighbors, however every vertex of $X_{uv} \cup \{v\}$ is self-private. Let $Z_{uv}$ be the lexicographically smallest set which has to be removed from $D'$ in order to make it minimal. Similarly, $Z_{uv}$ is obtained from the empty set by iteratively adding a vertex $z$ of smallest index in $D' \setminus Z_{uv}$ such that $z$ has no private neighbor with respect to $D' \setminus Z_{uv}$, until no such vertex exists. Since the elements of $X_{uv} \cup \{v\}$ are self-private in $D'$, the sets $X_{uv} \cup \{v\}$ and $Z_{uv}$ are disjoint, and non-adjacent. Let us finally set $D^* = ((D \setminus \{u\}) \cup X_{uv} \cup \{v\}) \setminus Z_{uv}$. Then $D^*$ is a minimal dominating set of $G$.

Observe that since $X_{uv}$ and $Z_{uv}$ are selected greedily with respect to $v_1, \dots, v_n$, this procedure is deterministic. Therefore, the procedure assigns to every minimal dominating set $D$ of $G$, and to every two vertices $u, v$ such that $u$ is in $D$ and is not isolated in $G[D]$, and $v \in \text{Priv}(D, u)$, a unique set $D^*$. We call $D^*$ the *parent of D* with respect to flipping $u$ and $v$, and denote it by $\text{Parent}_{uv}(D)$. The *parent of D*, denoted by $\text{Parent}(D)$, is defined as the set $\text{Parent}_{uv}(D)$ for the smallest possible choice of a pair $u, v$; note that $D$ has a unique parent according to this definition. Conversely, we denote by $\text{Children}(D^*)$ the set of all minimal dominating sets $D$ such that $D^* = \text{Parent}(D)$, and call *child of D*^* any element of $\text{Children}(D^*)$. We point that the size of such a set may be exponential in $n$. Note that, in the procedure, every edge in $G[D^*]$ is also an edge in $G[D]$, while there is at least one edge incident with $u$ that
<figure><img src="image_5.png" /><figcaption>Figure 3: An illustration of the flipping operation on a dominating set *D* such that *G[D]* contains at least one edge incident to some vertex *u*, here depicted by *uw*. Black vertices are elements of *D*, white vertices are some elements of *Priv(*D*, *u*). Dashed discs represent closed neighborhoods, and plain disks represent private neighborhoods.</figcaption></figure>

appears in $G[D]$ and not in $G[D^*]$. This simple but important observation was formalized as follows.

**Proposition 3.1 ([GHKV15]).** Let $D, D^* \in \mathcal{D}(G)$ be such that $D^* = \text{Parent}_{uv}(D)$ for some edge $uv$. Then $E(G[D^*]) \subsetneq E(G[D])$ and $v$ is an isolated vertex of $G[D^*]$.

The *flipping operation* is then defined to be the reverse of how $D^* = \text{Parent}_{uv}(D)$ was generated from $D$. This means, given $D^*$ with an isolated element $v \in D^*$, and $u$ a neighbor of $v$, the operation removes $X_{uv} \cup \{v\}$ and adds back $Z_{uv} \cup \{u\}$ to obtain a child $D$ of $D^*$ with respect to flipping $u$ and $v$. Obviously, the difficulty is to guess appropriate sets for $X_{uv}$ and $Z_{uv}$ when we are given only $D^*$, $u$, and $v$.

## 3.2 The flipping method

We now describe the flipping method as originally introduced in [GHKV15]. Assume that there exists an algorithm A that, given $D^* \in \mathcal{D}(G)$, enumerates a family $\mathcal{D}$ of minimal dominating sets of $G$ such that Children($D^*$) $\subseteq \mathcal{D}$ $\subseteq \mathcal{D}(G)$. We stress the fact that $\mathcal{D}$ may contain minimal dominating sets that are not actual children of $D^*$. The *flipping method*, then, consists of a depth-first search (DFS) on a directed solution graph $G$ whose nodes are minimal dominating sets of $G$, with one additional special node $r$, called the *root*, which has no in-neighbors. The out-neighbors of the root are the maximal independent sets of $G$ (which are minimal dominating sets), and there is an arc from a minimal dominating set $D^* \in V(G)$ to another one $D \in V(G)$ if A generates $D$ from $D^*$. At first, the DFS is initiated at the root. Its out-neighbors are generated with polynomial delay using the algorithm of Tsukiyama et al. [TIAS77]. The out-neighbors of the other nodes are generated using A. Since A outputs (in particular) every child of a given node, we can argue using Proposition 3.1 that every minimal dominating set is reachable from $r$. More solutions may however be output by A, and all the difficulty lies in handling the inherent repetitions.

In [GHKV15] and later papers [GHK$^+$16, GHK$^+$18], a list of already visited nodes of $\mathcal{G}$ is maintained in order to handle repetitions, inexorably requiring space that is linear in $\mathcal{D}(G)$, thus potentially exponential in $n$. The achieved time complexity, on the other hand, is incremental-polynomial.
**Lemma 3.2 ([GHKV15]).** Let $G$ be a graph. Suppose that there is an algorithm $A$ that, given $D^* \in \mathcal{D}(G)$, enumerates with polynomial delay a family $\mathcal{D}$ of minimal dominating sets of $G$ such that Children($D^*$) $\subseteq \mathcal{D}$ $\subseteq \mathcal{D}(G)$. Then there is an algorithm that enumerates with incremental delay the set $\mathcal{D}(G)$ of all minimal dominating sets of $G$.

We would like to mention that a similar proof allows for “incremental delay” instead of “polynomial delay” in the hypothesis of this statement. We further strengthen the statement in the following.

## 3.3 A polynomial-space flipping method

We show here that guiding the DFS toward the children, together with a folklore trick (see e.g. [BDH$^{+}$20, CS23] for recent formalizations) on running the algorithm again at each output, allows us to handle repetitions with polynomial space at the cost of an increased—but still incremental-polynomial-complexity.

The next lemma is central to the next section and may be regarded as a space improvement of Lemma 3.2. It is also of general interest as far as the flipping method is concerned.

**Lemma 3.3.** Let $G$ be an $n$-vertex graph, and $p, s: \mathbb{N} \to \mathbb{N}$ be non-decreasing polynomial functions. Suppose that there is an algorithm $A$ that, given $D^* \in \mathcal{D}(G)$, enumerates the $t$-th set of a family $\mathcal{D}$ satisfying Children($D^*$) $\subseteq \mathcal{D}$ $\subseteq \mathcal{D}(G)$ in time $p(n, t)$ and space $s(n)$. Then there is an algorithm that enumerates the $i$-th set of $\mathcal{D}(G)$ in

$$O(n^3) \cdot i^4 \cdot p(n, i)$$

time and $O(n^2) \cdot s(n)$ space.

*Proof.* In the following, let $\mathcal{G}'$ be the directed tree$^2$ on vertex set $V(\mathcal{G}') = \mathcal{D}(G) \cup \{r\}$ and edge set $E(\mathcal{G}') = \{(r, D) | D \in \text{MIS}(G)\} \cup \{(D^*, D) | D \in \text{Children}(D^*)\}$, where $r$ is a special vertex referred to as the *root*.

Let us first argue that every minimal dominating set $D$ is reachable from $r$ in $\mathcal{G}'$, by induction on the number of edges in it. If $D$ contains no edge, it is a maximal independent set, thus an out-neighbor of $r$. If $D$ contains an edge $uw$, consider such an edge with $u$ of smallest index in $D$, and its private neighbor $v$ of smallest index. Let $D^* = \text{Parent}(D)$, i.e., $D^*$ is obtained by flipping $u, v$. By Proposition 3.1, $D^*$ has fewer edges than $D$ and is thus reachable from $r$. There is an arc from $D^*$ to $D$ in $\mathcal{G}'$, hence the conclusion. Therefore, a DFS of $\mathcal{G}'$ initiated at $r$ visits all minimal dominating sets of $G$.

Furthermore, for every minimal dominating set $D$, the length of the path from $r$ to $D$ is at most $|E(G[D])| \le n^2$.

We now describe an algorithm $B$ that enumerates, possibly with repetitions, the set $\mathcal{D}(G)$ of all minimal dominating sets of $G$. When $B$ outputs a set that was not output before we call this output a *first occurrence*. The algorithm $B$ will output the $i$-th first occurrence (and so distinct solution) in

$$O(n^3) \cdot i^2 \cdot p(n, i)$$

time and $O(n^2) \cdot s(n)$ space. Algorithm $B$ proceeds as follows. First, it outputs every out-neighbor of $r$ without duplication using the algorithm of Tsukiyama et al. in [TIAS77]. Then, it proceeds with what boils down to a DFS (with additional outputs along the way) of $\mathcal{G}'$

<footnote>$^2$This forms a subgraph of $\mathcal{G}$ as defined in Section 3.2: Informally, the directed tree $\mathcal{G}'$ is what $\mathcal{G}$ would be if $A$ was reliable, i.e., only generated children of $D^*$.</footnote>
initiated at $r$, as follows. When visiting a node $D^* \in V(G')$, B seeks the children of $D^*$ by running A. Each set $D$ returned by A is first output by B. Then B checks whether $D$ is a child of $D^*$. If so, B “pauses” the execution of A on $D^*$, and launches A on $D$. When the execution of A on $D$ is complete, B “resumes” the execution of A on $D^*$.

Before, we discuss the time to compute first occurrences of B, we take a pause to determine the following: given $D$ and $D^*$ in $G'$, how fast can we determine if $D$ is a child of $D^*$? The naive approach we choose goes as follows: (1) consider the vertex of smallest index $u$ in $D$ such that there is an edge incident to $u$ in $G[D]$; (2) select the vertex $v$ of smallest index in $\text{Priv}(D, u)$; (3) perform the flipping operation along $u, v$; (4) check if the resulting set is $D^*$. Note that the selection of (1) and (2) can be done in $O(n^2)$ time. In order to make a flip when $u$ and $v$ are fixed, we need to compute the sets $X_{uv}$ and $Z_{uv}$. The straightforward approach does it in $O(n^3)$ time. Therefore, we can determine if $D$ is a child of $D^*$ in $O(n^3)$ time and $O(n^2)$ space (as for convenience, we work with the adjacency matrix).

We now examine the time spent by B to produce its $i$-th first occurrence. The outputs generated by the algorithm of Tsukiyama et al., so the maximal independent sets of $G$, are all first occurrences and are produced with $O(n^3)$ delay and $O(n^2)$ space, hence within the claimed time bound; see [TIAS77].

Let $D$ be a first occurrence output by B that is produced by a call of A on a node $D^*$ in $G'$. Say that $D$ is the $(i-1)$-th first occurrence in order output by B. Note that $D$ may or may not be a child of $D^*$. To obtain the next first occurrence output by B, we consider the path from $r$ to $D$ in $G'$ in case $D$ is a child of $D^*$, and the path from $r$ to $D^*$ in $G'$ otherwise. The algorithm B runs (or continue running) A on the last node of this path ($D$ or $D^*$), and for each node of the path, except $r$, B has on the stack a paused execution of A called on the node. In the worst case scenario, all these executions will be resumed and each of them will spend at most $p(n, i-1)$-time, hence $p(n, i)$-time as $p$ is increasing, producing solutions that were already output by B before. Moreover, if $D$ is a child of $D^*$, the execution of A on $D$ may produce a child $D'$ of $D$ that was already output by B before. In that later case, the execution of A is in turn paused, a recursive call is made on $D'$, and so on. However, this can happen only $i$ times since the nodes of $G'$ we explore that way are all distinct. So in total, at most $i$ such executions of A may, in a time bounded by $p(n, i)$ each, produce at most $i$ solutions that were already obtained by B. Hence the time spent by B between the $(i-1)$-th and the $i$-th first occurrences is bounded by $i \cdot p(n, i)$. Each obtained set is checked to see if it is a child of the current node of $G'$ in $O(n^3)$ time. Summing from 1 to $i$, B produces its $i$-th first occurrence or conclude that the $(i-1)$-th first occurrence was the last solution in a time which is bounded by $O(n^3) \cdot i^2 \cdot p(n, i)$. Moreover, within this time bound, the total number of sets output by B (with repetitions) is at most $i^2$.

We note that since $p$ is a polynomial and $i \le |\mathcal{D}(G)| \le 2^n$, there is a small constant $c$ such that B runs for at most $\text{poly}(n + 2^n) \le 2^{cn}$ time.

The space consumed by B is dominated by the space taken by at most $n^2$ paused executions of A and the adjacency matrix of $G$. Thus B runs in $O(n^2) \cdot s(n)$ space.

We are now ready to describe an algorithm C that enumerates $\mathcal{D}(G)$ without repetitions and within the desired time and space constraints. Algorithm C proceeds as follows. First, it launches a master instance of B. It also maintains a counter keeping track of the number of steps (i.e., elementary steps counted by the time complexity) of the master instance of B. Since B runs for at most $2^{cn}$ steps, a $cn$-bits long counter suffices. Whenever the master instance outputs a new set $D$, and the counter of steps indicates $j$, the algorithm C launches a new instance of B, runs it for $j-1$ steps, and compares each of its output with $D$. The new instance of B is killed after exactly $j-1$ steps. If $D$ did not appear as the output of the new instance, then
we conclude that it is a first occurrence of the master instance, and the algorithm C outputs D. If D has appeared as one of the outputs of the new instance, then C ignores it and continues the simulation of the master instance. In that way, every set of D(G) is output by C without repetitions.

We now examine the time spent by C to produce the i-th minimal dominating set. Recall that at most $i^2$ sets are output by the execution of B up to the i-th first occurrence. Thus, the number of new instances of B launched by C is bounded by $i^2$. Every such instance runs for at most $O(n^3) \cdot i^2 \cdot p(n, i)$ total time, as p is non-decreasing. Hence in total, C runs for at most

$$O(n^3) \cdot i^2 \cdot p(n, i) + i^2 \cdot O(n^3) \cdot i^2 \cdot p(n, i) = O(n^3) \cdot i^4 \cdot p(n, i)$$

time steps to produce the i-th solution.

The space consumed by C is determined by the space required by at most two independent instances of B running in the same time which is $2 \cdot O(n^2) \cdot s(n)$, and the size of the counter which is $O(n)$. Thus C runs in $O(n^2) \cdot s(n)$ space. □

The algorithms given in [GHKV15, GHK$^{+}$16, GHK$^{+}$18] for line graphs, graphs of girth at least 7, chordal bipartite graphs, and unit-square graphs rely on the flipping method and run in incremental-polynomial time and exponential space. By directly plugging in Lemma 3.3 instead of Lemma 3.2 in the procedure, we obtain the following.

**Corollary 3.4.** *There is an incremental-polynomial time and polynomial-space algorithm enumerating minimal dominating sets in line graphs, graphs of girth at least 7, chordal bipartite graphs, and unit-square graphs.*

# 4 Flipping method in comparability graphs

We now show how the flipping method, and more particularly the existence of an algorithm as required in Lemma 3.3, can be reduced to red-blue domination in comparability graphs.

Recall that Lemma 3.3 is stated for general graphs and that the family D to be constructed can contain arbitrarily many solutions that are not actual children. In [GHKV15], [GHK$^{+}$16] and [GHK$^{+}$18], the authors were able to provide such an algorithm A in line graphs, graphs of girth seven, chordal bipartite graphs and unit square graphs. In these last two cases, they proved that to obtain an efficient A, it suffices to design an efficient algorithm that enumerates all the minimal red dominating sets of an appropriate subgraph within the same class. We conduct a similar analysis to show that, in comparability graphs, it suffices to design an efficient algorithm that enumerates all the minimal red dominating sets of a subgraph in which blue vertices are minimal with respect to the associated poset.

Intuitively, the reason is that when flipping two adjacent vertices u, v with, say, $u \le v$, the set of private neighbors Y that the set $X_{uv} \cup \{v\}$ may steal are by definition incomparable to u, hence smaller than v. Moreover, the vertices in $Z_{uv}$ that had their private neighbors within Y are non-adjacent to v, hence larger that Y in the poset. Consequently, in the reverse operation, and in order to guess the appropriate sets $X_{uv}$ and $Z_{uv}$, we may focus on minimal sets that dominate Y from “above” and hence may restrict ourselves to the maximal elements in Y. This yields the desired red-blue domination instance.
<figure><img src="image_6.png" /><figcaption>Figure 4: A minimal dominating set $D$ (on the left) and its parent $D^* = \text{Parent}_{uv}(D)$ (on the right) represented by black vertices in the Hasse diagram of the underlying poset of a comparability graph. The edge induced by $D$ and incident to $u$ is depicted by $uw$.</figcaption></figure>

**Lemma 4.1.** Let $G$ be the comparability graph of a poset $P = (V, \leq)$. Suppose that there is an algorithm $B$ that, given an antichain $B$ of $P$ and a set $R \subseteq \uparrow B \setminus B$, enumerates with polynomial delay and polynomial space the set $\mathcal{D}(R, B)$ of minimal red dominating sets of $G(R, B)$. Then there is an algorithm $A'$ that, given $D^* \in \mathcal{D}(G)$ and $u, v \in V(G)$, enumerates with polynomial delay and polynomial space a family $\mathcal{D} \subseteq \mathcal{D}(G)$ containing all $D$ such that $D^* = \text{Parent}_{uv}(D)$.

*Proof.* The proof is conducted in the fashion of [GHK$^{+}$16]. We are given a minimal dominating set $D^*$ of $G$, an isolated vertex $v$ of $G[D^*]$, and a neighbor $u$ of $v$. Let us assume in the following that $u \leq v$ in $P$. The dual situation is handled by flipping upside-down the poset. This situation is depicted in Figure 4 (right). We aim to compute using $B$ a family of sets $\mathcal{D}$ such that $\{D \in \mathcal{D}(G) \mid D^* = \text{Parent}_{uv}(D)\} \subseteq \mathcal{D} \subseteq \mathcal{D}(G)$. Recall that the difficulty of computing such sets given $D^*$, $u$, and $v$, lies in guessing appropriate sets for $X_{uv}$ and $Z_{uv}$ in the definition of the Parent relation; see Section 3.1. To this purpose, we now define sets that we will then show to be containing $X_{uv}$ and $Z_{uv}$.

Let $R_1 \subseteq \uparrow u \cap D^*$ be the set of upper-neighbors of $u$ in $D^*$ such that $x \in \text{Priv}(D^*, x)$, i.e., these vertices are self-private in $D^*$. Note that in particular, $R_1$ is an antichain of $P$, and it contains $v$. Let $B = V(G) \setminus N[(D^* \setminus R_1) \cup \{u\}]$ be the set of all vertices that are not dominated anymore when replacing $R_1$ with $u$ in $D^*$. Note that $B \subseteq \downarrow R_1 \setminus R_1$ since $R_1 \subseteq \uparrow u$. Finally, let $R_2 = \uparrow B \setminus N[R_1]$. In particular, there are no edges between $R_1$ and $R_2$. Let us finally set $R = (R_1 \setminus \{v\}) \cup R_2$, and note that $B \subseteq \downarrow R \setminus R$. Informally, $R$ forms the set of vertices we can use to dominate $B$. We exclude $v$ from that set, since the whole point of the operation is to delete $v$. Note that $B$ and $R$ may be empty; we will focus on these cases later. Also $B$ is not necessarily an antichain. We now show that we can restrict our attention to the maximal elements of $B$, and to the part of $R$ that is adjacent to these elements.

The notation $\mathcal{D}(R \cap \uparrow \text{Max}(B), \text{Max}(B))$ below is blatantly cumbersome. To simplify the upcoming arguments, we prove that $\mathcal{D}(R \cap \uparrow \text{Max}(B), \text{Max}(B))$ is in fact equal to the conceptually simpler $\mathcal{D}(R, B)$.

**Claim 4.2.** The sets $\mathcal{D}(R, B)$ and $\mathcal{D}(R \cap \uparrow \text{Max}(B), \text{Max}(B))$ are equal.

*Proof.* Recall that $B \subseteq \downarrow R \setminus R$. We first note that every dominating set of $\text{Max}(B)$ in $R$ is a dominating set of $B$. Indeed, for every $x \in B$ there exists $y \in \text{Max}(B)$ such that $x \leq y$, and for any $x \in B$, $y \in \text{Max}(B)$, and $z \in R$, if $x \leq y$ and $yz$ is an edge, then $y \leq z$ and $xz$ is an edge. This guarantees $\mathcal{D}(R, \text{Max}(B)) \subseteq \mathcal{D}(R, B)$ as if an element of $R$ has a private neighbor in $\text{Max}(B)$, then it has in particular a private neighbor in $B$.
The converse inclusion is straightforward in the sense that every dominating set of $B$ is
in particular a dominating set of $\text{Max}(B)$. As we argued above, any subset of $R$ that domi-
nates $\text{Max}(B)$ dominates $B$. Therefore, by minimality, no proper subset of a set in $\mathcal{D}(R, B)$
dominates $\text{Max}(B)$. Hence $\mathcal{D}(R, B) \subseteq \mathcal{D}(R, \text{Max}(B))$ and so $\mathcal{D}(R, B) = \mathcal{D}(R, \text{Max}(B))$.

We conclude by observing that the elements in $R \setminus \uparrow \text{Max}(B)$ are not adjacent to the elements in $\text{Max}(B)$, hence that they do not appear in any minimal dominating set of $G(R, B)$. Consequently $\mathcal{D}(R, B) = \mathcal{D}(R \cap \uparrow \text{Max}(B), \text{Max}(B))$. $\sqsupset$

Let us now describe $A'$. First if $R = \emptyset$ and $B \neq \emptyset$, then $\mathcal{D}(R, B) = \emptyset$ and we return $\mathcal{D} = \emptyset$ as no $D$ satisfies $D^* = \text{Parent}_{uv}(D)$. Indeed in that case, $R_1 = \{v\}$, $B$ consists of the vertices that are not dominated anymore when replacing $v$ with $u$ in $D^*$, and since $B \subseteq \downarrow v$ and $R_2 = \uparrow B \setminus N[v] = \emptyset$, every attempt to dominate $B$ by adding vertices to $D' = (D^* \setminus \{v\}) \cup \{u\}$ will remove $v$ from the private neighbors of $u$ in $D'$. Since by definition $v$ is selected as a private neighbor of $u$ during the flipping operation, flipping $u$ and $v$ cannot produce a child of $D^*$ in that case. Otherwise $\mathcal{D}(R, B) \neq \emptyset$, and we enumerate all minimal red dominating sets in $\mathcal{D}(R, B)$ using $B$ with Claim 4.2. For each minimal red dominating set $X \in \mathcal{D}(R, B)$, we consider the set $D' = (D^* \setminus R_1) \cup \{u\} \cup X$ of vertices of $G$. Note that $X$ may be empty, in which case $B = \emptyset$ and $\mathcal{D}(R, B) = \{\emptyset\}$; that is not an issue. We greedily reduce $D'$ into an irredundant set $D$ of $G$, and output $D$.

This may seem counter-intuitive in an enumeration context, as a greedy reduction typically
does not explore all options. However, we will argue later (see Claim 4.6) that $D'$ is already
irredundant in all relevant cases, so $D = D'$ and the greedy reduction does not affect the pool
of children.

Let $\mathcal{D}$ be the multiset of all generated sets; we prove in the following four claims that $\mathcal{D}$ is in fact a set (no repetitions are produced) and that it has the desired properties. Namely, the correctness of $A'$ follows from Claims 4.3 and 4.6. We conclude the proof with the complexity analysis of $A'$.

**Claim 4.3.** All outputs produced by the above procedure are distinct. Moreover the elements of the set $\mathcal{D}$ are minimal dominating sets of $G$ and $|\mathcal{D}| = |\mathcal{D}(R, B)|$.

*Proof.* As there is a natural bijection between minimal red dominating sets $\mathcal{D}(R, B)$ and distinct outputs of $\mathcal{D}$, we only need to argue two things: that every output is a minimal dominating set, and that there is no repetitions.

There is nothing to argue in the case where $\mathcal{D}(R, B) = \emptyset$, and we assume from now on
that $\mathcal{D}(R, B)$ is non-empty. Let $X \in \mathcal{D}(R, B)$. To argue that its corresponding output is a
minimal dominating set, it suffices to argue that $(D^* \setminus R_1) \cup \{u\} \cup X$ is a dominating set since
we output an irredundant subset of it. Let $w$ be a vertex not dominated by $(D^* \setminus R_1) \cup \{u\}$.
By definition, it belongs to $B$, so $w \in N[X]$. Therefore, $(D^* \setminus R_1) \cup \{u\} \cup X$ is a dominating
set, as desired.

Finally, observe that when greedily reducing $(D^* \setminus R_1) \cup \{u\} \cup X$ into a minimal dominating set $D$, we maintain $X \subseteq D$ as each element of $X$ has a private neighbor in $B$. In fact, we have $D \cap R = X$, which guarantees that a different choice of $X$ would yield a different output $D$. $\sqsupset$

The next claim shows that the sets $X_{uv}$ and $Z_{uv}$ to guess lie in $R_1$ and $R_2$, respectively; see
Figure 3 for an example.

**Claim 4.4.** For any set $D \in \mathcal{D}(G)$ such that $D^* = \text{Parent}_{uv}(D)$, let $X_{uv}$ and $Z_{uv}$ be the disjoint sets defined in the Parent$_{uv}$ relation, so that $D = (D^* \cup \{u\} \cup Z_{uv}) \setminus (X_{uv} \cup \{v\})$. We have $X_{uv} \subseteq R_1 \setminus \{v\}$ and $Z_{uv} \subseteq R_2$. Additionally, for $Y_{uv} = \bigcup_{z \in Z_{uv}} \text{Priv}(D, z)$, we have $Y_{uv} \subseteq B$.
**Proof.** Recall that $Z_{uv}$ is defined as a set of vertices that lose their private neighbors with respect to $D$ when adding $X_{uv} \cup \{v\}$ to $D \setminus \{u\}$. These private neighbors are the elements of the set $Y_{uv}$.

By definition of the Parent relation, $G[D]$ contains an edge $uw$, and $v$ is selected in the set $\text{Priv}(D, u)$. Since $uw$ is an edge, one of $u \le w$ and $w \le u$ holds. As $v \in \text{Priv}(D, u)$ and $w \in D$, the vertices $v$ and $w$ are incomparable. Since $u \le v$, the case $w \le u$ would lead to a contradiction, and we derive $u \le w$.

Let us first argue that $X_{uv} \subseteq R_1 \setminus \{v\}$. We have $v \notin X_{uv}$, so we focus on proving $X_{uv} \subseteq R_1$. Recall that $X_{uv} \subseteq \text{Priv}(D, u) \setminus N[v]$ by definition. Since $u \le v$, $X_{uv}$ cannot be in $\downarrow u$ and so we derive $X_{uv} \subseteq \uparrow u \cap D^*$. It remains to argue that $x \in \text{Priv}(D^*, x)$ for every $x \in X_{uv}$. Since $X_{uv}$ is an independent set by construction, we have $x \in \text{Priv}(X_{uv}, x)$. Since $X_{uv} \cap N[v] = \emptyset$, we have $x \in \text{Priv}(X_{uv} \cup \{v\}, x)$. Since $X_{uv} \subseteq \text{Priv}(D, u)$, we derive $x \in \text{Priv}(X_{uv} \cup \{v\} \cup (D \setminus \{u\}), x)$, and so $x \in \text{Priv}(D^*, x)$ as $D^* \subseteq X_{uv} \cup \{v\} \cup (D \setminus \{u\})$. Hence $x \in R_1$ and it follows that $X_{uv} \subseteq R_1$.

Let us now argue that $Z_{uv} \subseteq R_2$ and $Y_{uv} \subseteq B$. Consider $z \in Z_{uv}$, and a private neighbor $y$ of $z$ with respect to $D$. Note that $y \in Y_{uv}$ and that $y$ is considered without loss of generality since every element of $Y_{uv}$ is the private neighbor of some element in $Z_{uv}$ with respect to $D$. Therefore, it suffices to argue that $z \in R_2$ and $y \in B$. Recall that $z$ has no private neighbor with respect to $(D \setminus \{u\}) \cup X_{uv} \cup \{v\}$, though $y$ is a private neighbor of $z$ with respect to $D$, which contains $u$. Since $X_{uv} \cup \{v\}$ and $Z_{uv}$ are non-adjacent, it follows that $z$ is not self-private (so $y \ne z$), and that $y$ is in the neighborhood of $X_{uv} \cup \{v\}$, but not in that of $u$. Since $X_{uv} \cup \{v\} \subseteq \uparrow u$ and $y \notin N(u)$, we have $y \notin \uparrow(X_{uv} \cup \{v\})$. We derive that $y \in \downarrow(X_{uv} \cup \{v\}) \setminus N[u]$. If $y \ge z$, then $z \in \downarrow(X_{uv} \cup \{v\})$, which contradicts the fact that $X_{uv} \cup \{v\}$ and $Z_{uv}$ are non-adjacent. So $y \le z$. Observe now that $z \notin N[R_1]$. Otherwise as $z \notin N[X_{uv} \cup \{v\}]$, either $z \in \downarrow R_1 \setminus (X_{uv} \cup \{v\})$ and then $y \in \downarrow R_1 \setminus (X_{uv} \cup \{v\})$, or $z \in \uparrow R_1 \setminus (X_{uv} \cup \{v\})$ and there is an element $r$ in $R_1 \setminus (X_{uv} \cup \{v\})$ such that $u \le r \le z$, hence such that $\text{Priv}(\{u, r, z\}, r) = \emptyset$. These two situations lead to a contradiction since the elements of $R_1 \setminus (X_{uv} \cup \{v\})$ are in $D$. So $z \notin N[R_1]$ and since $R_2 = \uparrow B \setminus N[R_1]$, the fact that $z \in R_2$ follows from $y \in B$, which we argue now.

We have $N(y) \cap D^* \subseteq X_{uv} \cup \{v\}$, as the only neighbor of $y$ in $D$ is $z$. As shown earlier, $X_{uv} \subseteq R_1$, hence $N(y) \cap D^* \subseteq R_1$. Since $u \notin N(y)$ and $B = V(G) \setminus N((D^* \setminus R_1) \cup \{u\})$, we derive $y \in B$, as desired. It follows that $Y_{uv} \subseteq B$ and $Z_{uv} \subseteq R_2$. ▼

The next claim shows that the set $X_{uv}$ to remove from $R_1$ and the set $Z_{uv}$ to find in $R_2$ can be found by computing minimal red dominating set of $G(R, B)$.

**Claim 4.5.** For any set $D \in \mathcal{D}(G)$ such that $D^* = \text{Parent}_{uv}(D)$, let $X_{uv}$ and $Z_{uv}$ be the disjoint sets defined in the Parent$_{uv}$ relation, so that $D = (D^* \cup \{u\} \cup Z_{uv}) \setminus (X_{uv} \cup \{v\})$. Then the set $R_1 \cup Z_{uv} \setminus (X_{uv} \cup \{v\})$ is a minimal red dominating set of $G(R, B)$.

**Proof.** Let $T = R_1 \cup Z_{uv} \setminus (X_{uv} \cup \{v\})$. By Claim 4.4, we obtain that $T \subseteq (R_1 \setminus \{v\}) \cup R_2 = R$. Therefore, it only remains to argue two things: that $T$ dominates $B$, and that $T$ is minimal, i.e., that every vertex in $T$ has a private neighbor in $B$ with respect to $T$.

Let $y \in B$. By definition of $B$, we have $N(y) \cap D^* \subseteq R_1 \cup \{v\}$ and $y \notin N[u]$. Since $D$ dominates $y$, and given how $D$ and $D^*$ relate, the vertex $y$ has a neighbor either in $R_1 \setminus (X_{uv} \cup \{v\})$ or in $Z_{uv}$. In either case, $y$ has a neighbor in $T$. We conclude that $T$ dominates $B$.

Let us now argue that every vertex $x$ in $T$ has a private neighbor in $B$ with respect to $T$. Note that $T \subseteq D$, hence that $x \in D$ and $\text{Priv}(D, x) \ne \emptyset$.

Let us first consider the case $x \in R_1 \setminus (X_{uv} \cup \{v\})$. Since $u \in D$, we have $\text{Priv}(D, x) \subseteq N[x] \setminus N[u]$. Since moreover $x \in \uparrow u$ we have that $\text{Priv}(D, x) \subseteq \downarrow x \setminus N[u]$. In particular
$x \notin \text{Priv}(D, x)$. Let $y \in \text{Priv}(D, x)$. Then $N(y) \cap D = \{x\}$ and so $N(y) \cap D^* \subseteq \{x\} \cup X_{uv} \cup \{v\} \subseteq R_1$. We conclude by definition of $B$ that $y \in B$. Therefore, every vertex in $T \cap (R_1 \setminus (X_{uv} \cup \{v\}))$ has a private neighbor in $B$ with respect to $T$.

We now consider the case $x \in Z_{uv}$. Let $y \in \text{Priv}(D, x)$. As $N(y) \cap D = \{x\}$ and $x \notin D^*$, we have $N(y) \cap D^* \subseteq X_{uv} \cup \{v\} \subseteq R_1$. Hence $y \in B$. Consequently every $x \in T$ has a private neighbor in $B$, and so $T \in \mathcal{D}(R, B)$. ▾

The core statement now follows easily.

**Claim 4.6.** *The set $\mathcal{D}$ contains every $D \in \mathcal{D}(G)$ such that $D^* = \text{Parent}_{uv}(D)$.*

*Proof.* Let $D \in \mathcal{D}(G)$ be such that $D^* = \text{Parent}_{uv}(D)$. Then $D^* = ((D \setminus \{u\}) \cup X_{uv} \cup \{v\}) \setminus Z_{uv}$, where $X_{uv}$ and $Z_{uv}$ are the disjoint sets defined in the Parent relation. Consider the set $Y_{uv} = \bigcup_{z \in Z_{uv}} \text{Priv}(D, z)$.

From Claim 4.5, we obtain that $R_1 \cup Z_{uv} \setminus (X_{uv} \cup \{v\})$ is a minimal dominating set of $G(R, B)$. Consequently, $B$ outputs $R_1 \cup Z_{uv} \setminus (X_{uv} \cup \{v\})$, which prompts $A'$ to consider the set $(D^* \setminus R_1) \cup \{u\} \cup (R_1 \cup Z_{uv} \setminus (X_{uv} \cup \{v\})) = (D^* \cup \{u\} \cup Z_{uv}) \setminus (X_{uv} \cup \{v\}) = D$ as a candidate to be output after being greedily reduced into an irredundant set. Note that the set is already irredundant, so $D$ is generated. In other words, we have $D \in \mathcal{D}$ as desired. ▾

Each of the sets $R_1, R_2, R$ and $B$ can be constructed in polynomial time in $n$. The same goes for computing and reducing $D'$ into a minimal dominating set given $T \in \mathcal{D}(R, B)$. In addition, $R \cap \text{↑Max}(B)$ and $\text{Max}(B)$ can be computed in polynomial time in $n$, and by Claim 4.2 the set $\mathcal{D}(R, B)$ can be generated with polynomial delay using $B$, concluding the proof. $\square$

We conclude this section with the following corollary of Lemma 3.3 and Lemma 4.1, observing that the antichain $B$ of a poset $P$ is minimal in $P[\text{↑}B]$. Note that while the algorithm $A'$ only computes the children $D$ for a fixed pair $u, v$, there are less than $n^2$ such pairs. Checking for each candidate $D$ if it is an actual child (for a minimal pair $u, v$) is done in polynomial time as argued in Section 3.1. Moreover, to avoid repetitions, we only output a child $D$ if the smallest pair of vertices $a, b$ in $D$ such that $D^* = \text{Parent}_{ab}(D)$ coincides with $u, v$. The obtained algorithm performs with polynomial delay (hence in incremental-polynomial time) and polynomial space, as desired.

**Theorem 4.7.** Let $\mathcal{G}$ be a graph class where every graph is comparability. If there is an incremental-polynomial time and polynomial-space algorithm enumerating minimal red dominating sets in red-blue graphs of $\mathcal{G}$ whose blue vertices are minimal with respect to the associated poset, then there is one enumerating minimal dominating sets in graphs of $\mathcal{G}$.

# 5 Red-blue domination in comparability graphs

We mentioned in Section 2 that RED-BLUE-DOM-ENUM is already as hard as TRANS-ENUM even restricted to bipartite graphs, hence to comparability graphs. We show nevertheless that the problem can be solved in incremental-polynomial time under various restrictions on the red and blue sets (satisfying those of Lemma 4.1), as well as on the underlying poset. More precisely, we show that, for any fixed integer $t$, RED-BLUE-DOM-ENUM is tractable in the comparability graph of $S_t$-free posets, whenever the blue elements are minimal in the poset. Since posets of bounded dimension do not contain any $S_p$ for some large enough $p$, we can derive the same for bounded dimension posets.
The key observation is that instances of red-blue domination in that case are of bounded conformality. As a corollary, we can use the algorithm of Khachiyan et al. in [KBEG07] to solve them in incremental-polynomial time. This yields by Theorem 4.7 an incremental-polynomial time algorithm enumerating minimal dominating sets in the comparability graphs of these posets.

Let us recall the notion of conformality introduced by Berge in [Ber84]. Informally, a hypergraph has small conformality when the property of not being contained in a hyperedge is witnessed by small subsets, in the sense that if a set is not contained in any hyperedge, then some small subset of it is not either. More formally, let $c$ be an integer and $\mathcal{H}$ be a hypergraph. We say that $\mathcal{H}$ is of conformality $c$ if the following property holds for every subset $X \subseteq V(\mathcal{H})$: $X$ is contained in a hyperedge of $\mathcal{H}$ whenever each subset of $X$ of cardinality at most $c$ is contained in a hyperedge of $\mathcal{H}$. Remember from Section 2 that a hypergraph $\mathcal{H}$ is Sperner if $E_1 \not\subseteq E_2$ for any two distinct hyperedges $E_1, E_2$ in $\mathcal{H}$.

Khachiyan, Boros, Elbassioni, and Gurvich proved the following; see also [Mar24] for a simple and general proof of this theorem.

**Theorem 5.1 ([KBEG07, Mar24]).** The minimal transversals can be enumerated in incremental-polynomial time but using exponential space in Sperner hypergraphs of bounded conformality.

Our result is a corollary of the following, which basically says that in our setting, hypergraphs with large conformality induce large $S_t$ in the underlying poset.

**Lemma 5.2.** Let $P = (V, \leq)$ be a poset, $B = \text{Min}(P)$ and $R = P - B$. Let $\mathcal{H}$ be the Sperner hypergraph defined by $V(\mathcal{H}) = P - B$ and

$$ \mathcal{E}(\mathcal{H}) = \text{Min}_{\subseteq} \{\uparrow x \setminus \{x\} \mid x \in B\}. $$

If $\mathcal{H}$ is not of conformality $t-1$ for some integer $t$, then $P$ contains $S_t$ as a suborder.

*Proof.* Assume that $\mathcal{H}$ is not of conformality $t-1$, i.e., there is a subset $X \subseteq V(\mathcal{H})$ that is not contained in a hyperedge of $\mathcal{H}$, and such that every subset $Y \subseteq X$ of size at most $t-1$ is contained in a hyperedge of $\mathcal{H}$. We consider $X = \{x_1, \dots, x_p\}$ of minimum cardinality. Then $p \geq t$ and to every $x_i \in X$ corresponds a hyperedge $E_i$ of $\mathcal{H}$ such that $E_i \cap X = \{X \setminus \{x_i\}\}$. Indeed, if no such $E_i$ exists for some $x_i \in X$, then $X' = X \setminus \{x_i\}$ is not contained in a hyperedge of $\mathcal{H}$, and still every subset $Y \subseteq X'$ of size at most $t-1$ is, contradicting the minimality of $X$.

Let us show that $X$ is an antichain of $P$. Suppose toward a contradiction that $X$ is not an antichain and contains two elements $x_i, x_j$ such that $x_i < x_j$. As $R \subseteq \uparrow B \setminus B$, every hyperedge of $\mathcal{H}$ that contains $x_i$ contains $x_j$. We conclude that $X \subseteq E_j$, a contradiction. Hence $X$ is an antichain.

Consider now the antichain $\{e_1, \dots, e_p\} \subseteq B$ corresponding to $E_1, \dots, E_p$ in the poset $P$, i.e., such that $E_i = \uparrow e_i \setminus \{e_i\}$ for $i \in \{1, \dots, p\}$. Then the set $\{e_1, x_1, \dots, e_p, x_p\}$ induces $S_p$ as suborder, $p \geq t$. $\square$

Lemmas 3.3, 4.1, and 5.2 together yield the following corollary.

**Corollary 5.3.** There is an algorithm enumerating, for every fixed integer $t$, the minimal dominating sets in comparability graphs of $S_t$-free posets.

Theorem 1.2 follows from Corollary 5.3 and the observation that a poset containing $S_t$ has dimension at least $t$. Unfortunately, as the algorithms in [KBEG07, Mar24] require exponential space, Corollary 5.3 does not yield a polynomial-space algorithm.

Finally, we note that while it is not clear whether the comparability graphs of bounded dimension posets are of bounded LMIM-width (and hence covered by the algorithm in [GHK$^{+}$18] using similar methods), comparability graphs of $S_t$-free posets are not.
# 6 Minimal dominating sets in incomparability graphs

We give a polynomial-delay algorithm enumerating minimal dominating sets in the incomparability graphs of bounded dimension posets, given with linear extensions witnessing the dimension. Although it is not necessary, we present a geometrical representation of the incomparability graphs that we find useful while working with them.

Let $P = (V, \leqslant)$ be a poset on $n$ elements and of dimension at most $d$. Let $\leqslant_1, \dots, \leqslant_d$ be a sequence of linear orders witnessing it. Thus, we have $x \leqslant y$ in $P$ if and only if $x \leqslant_i y$ for each $i \in \{1, \dots, d\}$. Consider $d$ distinct vertical lines $L_1, \dots, L_d$ in the plane, sorted from left to right in that order. For each $i \in \{1, \dots, d\}$, we distinguish $n$ points on $L_i$ and label them bottom-up with elements of $P$ sorted by $\leqslant_i$. Now for each element $v$ in $P$, we define a piecewise linear curve $\bar{v}$ consisting of $d-1$ segments and connecting points labelled $v$ on consecutive lines. It is a folklore observation, see e.g. [GRU83], that the incomparability graph of $P$ is the intersection graph of this family of curves. An example for $d=4$ is given in Figure 5.

In the remaining of this section, we assume that a poset $P = (V, \leqslant)$ of dimension $d$ is given and we are also given the total orders $\leqslant_1, \dots, \leqslant_d$ witnessing the dimension of $P$. As described above we fix the lines $L_1, \dots, L_d$, and the piecewise linear curves representing each element of $P$. Let $G$ be the incomparability graph of $P$.

For a non-empty subset $S$ of elements of $P$ and $i \in \{1, \dots, d\}$, we define $L_i(S)$ to be the maximum element of $S$ in $\leqslant_i$. We call vertices upwards from $S$ the elements of the set

$$U(S) = \{v \in V \setminus S \mid L_i(S) <_i v \text{ for some } i \in \{1, \dots, d\}\}.$$

A set $D$ is an *upward extension* of $S$ if $S \subseteq D$ and $D \setminus S \subseteq U(S)$.

Let $S$ be a subset of elements of $P$ of size at least $3d$. We call the *first layer* of $S$ the tuple $A(S) = (a_1, \dots, a_d)$ so that $a_1 = L_1(S)$, and for every $i \in \{2, \dots, d\}$,

$$a_i = L_i(S \setminus \{a_1, \dots, a_{i-1}\}).$$

Note that by this definition it might happen that $a_i \neq L_i(S)$. This is in particular the case if $L_i(S) = L_j(S)$ for some $i, j \in \{1, \dots, d\}$ with $j < i$. The *second layer* of $S$ is the set $B(S) = A(S \setminus A(S))$. The *third layer* of $S$ is the set $C(S) = A(S \setminus (A(S) \cup B(S)))$. Note that since $|S| \geqslant 3d$, the three layers are well-defined. We call the *border* of $S$ the concatenation

$$T(S) = (a_1, \dots, a_d, b_1, \dots, b_d, c_1, \dots, c_d)$$

of these three layers. In the following, we will consider irredundant such $S$. The reason for considering three layers is to help characterizing, in the coming proof, where the private neighbors of the elements in $B(S)$ lie, namely, “between” the elements of $A(S)$ and $C(S)$.

We say that $I$ can be *extended upwards into a minimal dominating set* whenever there is an upward extension of $I$ that is a minimal dominating set of $G$. In the following, we aim to decide in polynomial time whether a given irredundant set $I$ in $G$ can be extended upwards into a minimal dominating set. When the given set $I$ is of size at most $3d$, say $I = \{x_1, \dots, x_p\}$ and $p \leqslant 3d$, then this can be done efficiently by checking for all the tuples $(y_1, \dots, y_p) \in \text{Priv}(I, x_1) \times \dots \times \text{Priv}(I, x_p)$ whether $U(I) \setminus N[y_1, \dots, y_p]$ dominates $G - N[I]$ or not. A single tuple like that could be verified in $O(n^2)$ time. Since the number of tuples is no more than $n^p$, the total time is $O(n^{3d+2})$. If there is such a tuple $(y_1, \dots, y_p)$, then $U(I) \setminus N[y_1, \dots, y_p]$ can be greedily reduced into a minimal set $X$ so that $I \cup X$ is a minimal dominating set of $G$. Otherwise, we know that $I$ cannot be extended as we explored all the possibilities for $I$ to keep its private neighbors in an upward extension. This may be seen as an adaptation of the
<figure><img src="image_7.png" /><figcaption>Figure 5: A poset *P* and its incomparability graph *G* as an intersection graph of curves induced by four linear extensions witnessing the dimension.</figcaption></figure>

algorithm by Boros et al. for the extension of subsets of constant size [BGH98] to our ordered
context.

The point of the following is to show that the same technique can be applied for irredund-
dant sets of arbitrary size. The key insight is that it is enough to check whether we can extend
$I$ into a dominating set so that all elements in the border $T(I)$ keep a private neighbor, with
$T(I)$ being of constant size for fixed values of $d$.

**Theorem 6.1.** Let $I$ be an irredundant set of $G$ of size at least $3d$ and let $T(I) = (t_1, \dots, t_{3d})$.
Then $I$ can be extended upwards into a minimal dominating set of $G$ if and only if there exists a tuple $(w_1, \dots, w_{3d}) \in \text{Priv}(I, t_1) \times \dots \times \text{Priv}(I, t_{3d})$ such that $U(I) \setminus N[\{w_1, \dots, w_{3d}\}]$ is a dominating set of $G - N[I]$.

*Proof.* First, we prove the forward implication. Suppose that $I$ can be extended upwards into a minimal dominating set of $G$ and let $X \subseteq U(I)$ be such that $D = I \cup X$ is a minimal dominating set of $G$. Then $X$ dominates $G - N[I]$ and $\text{Priv}(D, u) \neq \emptyset$ for every $u \in D$. Thus there exists a tuple $(w_1, \dots, w_{3d})$ in $\text{Priv}(D, t_1) \times \dots \times \text{Priv}(D, t_{3d})$, which, by definition, is such that $X \cap N[\{w_1, \dots, w_{3d}\}] = \emptyset$. Note that $\text{Priv}(D, t_i) \subseteq \text{Priv}(I, t_i)$ for each $i \in \{1, \dots, 3d\}$, hence that $(w_1, \dots, w_{3d})$ belongs to $\text{Priv}(I, t_1) \times \dots \times \text{Priv}(I, t_{3d})$ as well. This completes the proof of the forward implication.

We now turn to the backward implication. Intuitively, we aim to show in the following that
a vertex from $U(I)$ may not steal a private neighbor of a vertex in $I \setminus T(I)$ without stealing
the private neighbors of a vertex in $T(I)$, namely, one in $B(I)$. To prove this, we will show
that the piecewise linear curves of the elements in $T(I)$ "separate" the curves of the private
neighbors of the elements in $I \setminus T(I)$ from the curves of elements in $U(I)$.

Suppose that there exists $(w_1, \dots, w_{3d}) \in \text{Priv}(I, t_1) \times \dots \times \text{Priv}(I, t_{3d})$ such that $X :=
U(I) \setminus N[\{w_1, \dots, w_{3d}\}]$ dominates $G - N[I]$. Thus $D = I \cup X$ dominates $G$. In order
to conclude that $I$ extends upwards into a minimal dominating set of $G$, all we need to see
is that each element $u$ in $I$ has a private neighbor with respect to $D$, i.e., $\text{Priv}(D, u) \neq \emptyset$.
Indeed, if so, then $D$ can be reduced into a minimal dominating set with the desired property
that $D \setminus I \subseteq U(S)$. Since $X$ avoids $N[\{w_1, \dots, w_{3d}\}]$, we have that $w_i \in \text{Priv}(D, t_i)$ for
each $i \in \{1, \dots, 3d\}$. Consider any element $u$ in $I \setminus T(I)$. Since $I$ is irredundant, we can fix $v \in \text{Priv}(I, u)$. We shall show that $v \in \text{Priv}(D, u)$.

For convenience, we split the sequence $(t_1, \dots, t_{3d})$ into three sequences $(a_1, \dots, a_d)$, $(b_1, \dots, b_d)$, and $(c_1, \dots, c_d)$, so it relates to the initial layers $\mathbf{A}(I)$, $\mathbf{B}(I)$, and $\mathbf{C}(I)$, respectively.

In order to get a contradiction, suppose that there is $x \in X$ such that $x$ and $v$ are adjacent in $G$, i.e., $\bar{x}$ and $\bar{v}$ intersect. In particular, there is some $q \in \{1, \dots, d\}$ such that $x <_q v$.

We claim that

$$v < b_k \text{ in } P \text{ for every } k \in \{1, \dots, d\}.$$

Since $v \in \text{Priv}(I, u)$ and $b_k \in I$, $\bar{v}$ and $\bar{b}_k$ do not intersect. Therefore, either $v < b_k$ in $P$ or $v > b_k$ in $P$. Assume toward a contradiction that $b_k < v$ in $P$. Since $\bar{u}$ and $\bar{v}$ intersect, we can fix $p \in \{1, \dots, d\}$ such that $v <_p u$. Recall that $u \in I \setminus T(I)$. Thus, by the definition of the third layer $\mathbf{C}(I)$ we have $u <_p c_p$. Hence $v <_p u <_p c_p$. Since $v \in \text{Priv}(I, u)$ and $c \in I$, we have that $\overline{c_p}$ and $\overline{v}$ are disjoint. We deduce that $v < c_p$ in $P$. This contradicts our assumption as $b_k < v < c_p$ in $P$ but, by construction, no element of the second layer can be below an element of the third layer. This completes the proof of the claim.

In particular, we have $x <_q v <_q b_k$ for every $k \in \{1, \dots, d\}$.

Consider the tuple $(s_1, \dots, s_d) = (w_{d+1}, \dots, w_{2d})$ of private neighbors of the elements of $(b_1, \dots, b_d)$. We claim that there exist indices $\alpha, \beta \in \{1, \dots, d\}$ such that

$$b_{\alpha} <_q s_{\beta}.$$

Towards the contradiction, assume that $s_i <_q b_j$ for all $i, j \in \{1, \dots, d\}$. Since $\overline{s_i}$ and $\overline{b_j}$ are non-intersecting for $i \neq j$, we conclude that $s_i < b_j$ in $P$ for every $i \neq j$. Since $\overline{s_i}$ intersects $\overline{b_i}$, there is an index $t(i)$ so that $b_i <_{t(i)} s_i$, for each $i \in \{1, \dots, d\}$. Clearly, the values $t(i)$ must be all distinct for $i \in \{1, \dots, d\}$. This way, we need to take $d$ distinct values for $t_i$'s and because of our assumption all of them are in $\{1, \dots, d\} \setminus \{q\}$. We obtain a contradiction, proving the claim.

We concluded so far that

$$x <_q v <_q b_{\alpha} <_q s_{\beta}.$$

Now recall that $x \in X \subseteq \mathbf{U}(I)$. Thus, there must be some $p \in \{1, \dots, d\}$ with

$$\mathbf{L}_p(I) <_p x.$$

Recall also that $\overline{s_{\beta}}$ intersects $\overline{b_{\beta}}$, so we can fix $t \in \{1, \dots, d\}$ such that $s_{\beta} <_t b_{\beta}$. By the definition of the first two layers, we have that $b_{\beta} <_t a_t$. Thus, $s_{\beta} <_t a_t$. Since $s_{\beta} \in \text{Priv}(I, b_{\beta})$ and $a_t \in I$, we get that $\overline{s_{\beta}}$ and $\overline{a_t}$ are non-intersecting. Therefore, $s_{\beta} < a_t$ in $P$. In particular, we get $s_{\beta} <_p a_t$ and

$$s_{\beta} <_p a_t \leq_{p} \mathbf{L}_p(I) <_p x.$$

The two inequalities $s_{\beta} >_q x$ and $s_{\beta} <_p x$ imply that $\bar{x}$ intersects $\overline{s_{\beta}}$. Thus $x$ and $s_{\beta}$ are adjacent in $G$. This contradicts the assumption that $X \subseteq \mathbf{U}(I) \setminus N[s_{\beta}]$ and completes the proof of the backward implication. $\square$

We deduce the next corollary, by guessing a good tuple $(w_1, \dots, w_{3d})$ as in Theorem 6.1 in case when $|I| \ge 3d$, and checking for such a tuple whether the set $\mathbf{U}(I) \setminus N[\{w_1, \dots, w_{3d}\}]$ is a dominating set of $G - N[I]$. Space is polynomial as we only iterate through neighborhoods.

**Corollary 6.2.** There is an algorithm that, given an irredundant set $I$ of $G$, decides in $O(n^{3d+2})$ time and polynomial space whether $I$ can be extended upwards into a minimal dominating set.
We are now ready to describe a simple algorithm enumerating minimal dominating sets in the incomparability graphs of bounded dimension posets. The algorithm will construct solutions one vertex at a time, guaranteeing that every partial solution extends to a minimal dominating set, in a fashion similar to the *flashlight search* technique [SM19, CS21]. The following Parent relation between partial solutions will be used by the algorithm to handle repetitions.

**Definition 6.3.** Let $I$ be a non-empty irredundant set of $G$ that can be extended upwards into a minimal dominating set. We call parent of $I$ the unique irredundant set $I^* = \text{Parent}(I)$ obtained by removing vertex $L_1(I)$ from $I$, i.e., the greatest vertex $v$ in $I$ with respect to $<_1$.

Observe that every minimal dominating set $D$ of $G$ is an irredundant set of $G$ that can be extended upwards into a minimal dominating set (the extension being $D$ itself), with no children. Conversely, an irredundant set that can be extended upwards into a minimal dominating set, with no children, is necessarily a minimal dominating set.

Consequently, the Parent relation as introduced in Definition 6.3 defines a tree $T$ whose nodes are irredundant sets of $G$ that can be extended upwards into minimal dominating sets, root is the empty set, leaves are minimal dominating sets of $G$, and where there is an edge between two irredundant sets $I^*$ and $I$ if $I^* = \text{Parent}(I)$. The fact that all minimal dominating sets appear as leaves of this tree follows by induction noting that each node of $T$ distinct from the root has a parent whose cardinal is strictly smaller. As in Section 3, the enumeration proceeds with what boils down to a DFS of $T$ initiated at the empty set. When visiting a node $I^* \in V(T)$, the algorithm seeks the children of $I$ as follows. It checks for every candidate vertex $v \in U(I^*)$ whether $I^* \cup \{v\}$ can be extended upwards into a minimal dominating set, using Corollary 6.2, and whether the obtained set is a child of $I^*$, using Definition 6.3. Whenever it is the case, the algorithm “pauses” the generation of children of $I^*$, and generates children of $I^* \cup \{v\}$. When the generation on $I^* \cup \{v\}$ is complete, the algorithm “resumes” the generation on $I^*$. During this procedure, only the leaves of $T$, hence the minimal dominating sets of $G$, are output by the algorithm. Duplications are implicitly avoided by the structure of $T$.

The delay time complexity is bounded by twice the depth of the tree (the maximal distance between two leaves in $T$), times the time complexity of solving the extension problem and checking the Parent relation, for every candidate vertex $v$. This sums up to

$$2n \cdot O(n^{3d+2} + n^2) \cdot n = O(n^{3d+4})$$

Space complexity is polynomial as we only need to store for each node $W \in T$ from the root to the current node $I^* \in T$ the data of the (paused) execution of the children generation on node $W$.

We conclude to Theorem 1.1 that we restate here with the complexity.

**Theorem 6.4.** There is an algorithm that, given the incomparability graph $G$ of an $n$-element poset $P$ of dimension $d$, together with $d$ linear orders witnessing the dimension of $P$, enumerates all minimal dominating sets of $G$ with delay $O(n^{3d+4})$ and using polynomial space.

# 7 Discussions

In this paper, we provided an incremental-polynomial (resp. polynomial-delay) algorithm enumerating the minimal dominating sets in the comparability (resp. incomparability) graphs of bounded dimension posets. Recall that the complexity of TRANS-ENUM, which reduces to DOM-ENUM in co-bipartite graphs, is widely open. As incomparability graphs include co-bipartite
graphs, dropping the dimension in Theorem 1.1 is one of the most important algorithmic challenges in enumeration. On the other hand, dropping the dimension in Theorem 1.2 seems a more tractable, though fascinating challenge.

The algorithm provided by Corollary 5.3 covers in fact all comparability graphs of $S_t$-free posets, not just those of bounded dimension. The two first authors initiated in [BDH$^+$20] a characterization of the complexity of Dom-ENUM in $H$-free graphs. Despite the fact that they encapsulate all the hardness of Dom-ENUM, incomparability graphs have a restrictive structure. What can we say about $H$-free incomparability graphs? Due to co-bipartite graphs, this question is only interesting for a co-bipartite $H$. To match Theorem 1.2, it is tempting to wonder what happens for incomparability graphs of $S_t$-free posets. Our proof clearly does not extend naturally, as it crucially relies on the bounded dimension representation—recall that not all $S_t$-free posets have small dimension [Tro92]. However, we believe that an extension would be possible with different tools.

**Conjecture 7.1.** For every $t$, there is an output-polynomial time algorithm for Dom-ENUM in incomparability graphs of $S_t$-free posets.

A directly easier conjecture is the following:

**Conjecture 7.2.** For every $p$, there is an output-polynomial time algorithm for Dom-ENUM in $2K_p$-free incomparability graphs.

Indeed, note that an $S_{2p}$ suborder in a poset yields a $2K_p$ in the corresponding incomparability graph, where $2K_p$ denotes two disjoint cliques on $p$ elements. Symmetrically, Corollary 5.3 implies that for every $p$, there is an output-polynomial time algorithm for Dom-ENUM in $K_{p,p}$-free comparability graphs. Conjecture 7.2 holds trivially for $p=1$ (all such graphs are cliques). It is in fact also true for $p=2$, as $2K_2$-free graphs admit an output-polynomial time algorithm [BDH$^+$20]. The case $p=3$ is widely open without the incomparability assumption [BDH$^+$20].

Questions abound around Conjecture 7.2, mainly by considering other simple cases of a co-bipartite $H$. The case $H = C_4$ is the smallest open case for general graphs, but $C_4$-free incomparability graphs are interval graphs [GH64]; there Dom-ENUM admits a linear delay algorithm [KLM$^+$13]. A natural generalization would be the case of $H$ being two cliques with a matching between them, or $H$ being a clique minus a matching. Instead of debating which generalizations are most sensible, we state the following bold conjecture:

**Conjecture 7.3.** For any co-bipartite $H$, there is an output-polynomial time algorithm for Dom-ENUM in $H$-free incomparability graphs.

There is in fact no blatant reason why the incomparability condition would be necessary here. Other natural parameters for the classes considered in this paper concern the height and width of the poset. The *height* (resp. *width*) of a poset is the size of its maximum chain (resp. antichain). Since those are related to the largest size of a clique, the algorithm in [BDH$^+$20] covers the comparability graphs of posets of bounded height and the incomparability graphs of posets of bounded width. We can show easily that Dom-ENUM is tractable in the comparability graphs of posets of bounded width.

**Proposition 7.4.** Let $G$ be the comparability graph of a poset $P = (V, \leqslant)$ of width $\alpha$, and $D$ be a minimal dominating set of $G$. Then $|D| \leqslant 2\alpha$.

*Proof.* Consider for a contradiction a minimal dominating set $D$ of $G$ with $|D| > 2\alpha$. Then $D$ contains three elements $x, y, z$ such that $x < y < z$. As a consequence, $N[y] \subseteq N[x] \cup N[z]$, which contradicts $\text{Priv}(D, y) \neq \emptyset$. $\square$
Proposition 7.4 guarantees that a brute-force test of all small subsets yields a polynomial-time algorithm enumerating minimal dominating sets in the comparability graph of posets of bounded width.

As for incomparability graphs of posets of height 2, we consider the incompatibilities of a bipartite order and observe that all co-bipartite graphs can be represented as incomparability graphs of a poset of height at most 2. Therefore, bounded height is not a helpful parameter for incomparability graphs. A more interesting question is perhaps whether restricting posets to lattices yields efficient algorithms, both for comparability and incomparability graphs.

Our algorithm for incomparability graphs of bounded dimension relies heavily on their geometric representation, as in [GHK$^{+18}$]. An open question is whether we can achieve polynomial delay without the representation.

## References

[BDH$^{+20}$] Marthe Bonamy, Oscar Defrain, Marc Heinrich, Michał Pilipczuk, and Jean-Florent Raymond. Enumerating minimal dominating sets in $K_t$-free graphs and variants. *ACM Transactions on Algorithms (TALG)*, 16(3):1–23, 2020.

[BDHR19] Marthe Bonamy, Oscar Defrain, Marc Heinrich, and Jean-Florent Raymond. Enumerating minimal dominating sets in triangle-free graphs. In *36th International Symposium on Theoretical Aspects of Computer Science*. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.

[BEGK04] Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Leonid Khachiyan. Generating maximal independent sets for hypergraphs with bounded edge-intersections. In *Latin American Symposium on Theoretical Informatics*, pages 488–498. Springer, 2004.

[Ber84] Claude Berge. Hypergraphs: combinatorics of finite sets, volume 45. Elsevier, 1984.

[BGH98] Endre Boros, Vladimir Gurvich, and Peter L Hammer. Dual subimplicants of positive boolean functions. *Optimization Methods and Software*, 10(2):147–156, 1998.

[CHvHK13] Jean-François Couturier, Pinar Heggernes, Pim van’t Hof, and Dieter Kratsch. Minimal dominating sets in graph classes: combinatorial bounds and enumeration. *Theoretical Computer Science*, 487:82–94, 2013.

[CKP$^{+19}$] Nadia Creignou, Markus Kröll, Reinhard Pichler, Sebastian Skritek, and Heribert Vollmer. A complexity theory for hard enumeration problems. *Discrete Applied Mathematics*, 2019.

[Cou09] Bruno Courcelle. Linear delay enumeration and monadic second-order logic. *Discrete Applied Mathematics*, 157(12):2675–2700, 2009.

[CS21] Florent Capelli and Yann Strozecki. Enumerating models of dnf faster: breaking the dependency on the formula size. *Discrete Applied Mathematics*, 303:203–215, 2021.
[CS23] Florent Capelli and Yann Strozecki. Geometric amortization of enumeration algorithms. In *40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)*. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2023.

[DM41] Ben Dushnik and Edwin W. Miller. Partially ordered sets. *American journal of mathematics*, 63(3):600–610, 1941.

[DN19] Oscar Defrain and Lhouari Nourine. Neighborhood inclusions for minimal dominating sets enumeration: Linear and polynomial delay algorithms in $P_7$-free and $P_8$-free chordal graphs. In *30th International Symposium on Algorithms and Computation*. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019.

[EG95] Thomas Eiter and Georg Gottlob. Identifying the minimal transversals of a hypergraph and related problems. *SIAM Journal on Computing*, 24(6):1278–1304, 1995.

[EGM03] Thomas Eiter, Georg Gottlob, and Kazuhisa Makino. New results on monotone dualization and generating hypergraph transversals. *SIAM Journal on Computing*, 32(2):514–537, 2003.

[EMG08] Thomas Eiter, Kazuhisa Makino, and Georg Gottlob. Computational aspects of monotone dualization: A brief survey. *Discrete Applied Mathematics*, 156(11):2035–2049, 2008.

[FGPS08] Fedor V. Fomin, Fabrizio Grandoni, Artem V. Pyatkin, and Alexey A. Stepanov. Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications. *ACM Transactions on Algorithms*, 5(1):9, 2008.

[FK96] Michael L. Fredman and Leonid Khachiyan. On the complexity of dualization of monotone disjunctive normal forms. *Journal of Algorithms*, 21(3):618–628, 1996.

[GH64] Paul C. Gilmore and Alan J. Hoffman. A characterization of comparability graphs and of interval graphs. *Canadian Journal of Mathematics*, 16:539–548, 1964.

[GHK$^{+}$16] Petr A. Golovach, Pinar Heggernes, Mamadou M. Kanté, Dieter Kratsch, and Yngve Villanger. Enumerating minimal dominating sets in chordal bipartite graphs. *Discrete Applied Mathematics*, 199:30–36, 2016.

[GHK$^{+}$18] Petr A. Golovach, Pinar Heggernes, Mamadou M. Kanté, Dieter Kratsch, Sigve H. Sæther, and Yngve Villanger. Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. *Algorithmica*, 80(2):714–741, 2018.

[GHKV15] Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, and Yngve Villanger. An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. *Algorithmica*, 72(3):836–859, 2015.

[GKLS19] Petr A. Golovach, Dieter Kratsch, Mathieu Liedloff, and Mohamed Yosri Sayadi. Enumeration and maximum number of minimal dominating sets for chordal graphs. *Theoretical Computer Science*, 783:41–52, 2019.

[GRU83] Martin C. Golumbic, Doron Rotem, and Jorge Urrutia. Comparability graphs and intersection graphs. *Discrete Mathematics*, 43(1):37–46, 1983.
[JYP88] David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. On generating all maximal independent sets. *Information Processing Letters*, 27(3):119-123, 1988.

[KBEG07] Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Vladimir Gurvich. On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs. *Theoretical Computer Science*, 382(2):139-150, 2007.

[KKP18] Mamadou M. Kanté, Kaveh Khoshkhah, and Mozhgan Pourmoradnasseri. Enumerating minimal transversals of hypergraphs without small holes. In *43rd International Symposium on Mathematical Foundations of Computer Science*. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.

[KLM$^{+13}]$ Mamadou M. Kanté, Vincent Limouzy, Arnaud Mary, Lhouari Nourine, and Takeaki Uno. On the enumeration and counting of minimal dominating sets in interval and permutation graphs. In *International Symposium on Algorithms and Computation*, pages 339-349. Springer, 2013.

[KLM$^{+15a}$] Mamadou M. Kanté, Vincent Limouzy, Arnaud Mary, Lhouari Nourine, and Takeaki Uno. A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs. In *International Workshop on Graph-Theoretic Concepts in Computer Science*, pages 138-153. Springer, 2015.

[KLM$^{+15b}$] Mamadou M. Kanté, Vincent Limouzy, Arnaud Mary, Lhouari Nourine, and Takeaki Uno. Polynomial delay algorithm for listing minimal edge dominating sets in graphs. In *Workshop on Algorithms and Data Structures*, pages 446-457. Springer, 2015.

[KLMN14] Mamadou M. Kanté, Vincent Limouzy, Arnaud Mary, and Lhouari Nourine. On the enumeration of minimal dominating sets and related notions. *SIAM Journal on Discrete Mathematics*, 28(4):1916-1929, 2014.

[Mar24] Arnaud Mary. Enumeration of minimal transversals of hypergraphs of bounded vc-dimension. *arXiv preprint arXiv:2407.00694*, 2024.

[MU04] Kazuhisa Makino and Takeaki Uno. New algorithms for enumerating all maximal cliques. In *Scandinavian workshop on algorithm theory*, pages 260-272. Springer, 2004.

[SM19] Yann Strozecki and Arnaud Mary. Efficient enumeration of solutions produced by closure operations. *Discrete Mathematics & Theoretical Computer Science*, 21, 2019.

[Str19] Yann Strozecki. Enumeration complexity. *Bulletin of EATCS*, 1(129), 2019.

[TIAS77] Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa. A new algorithm for generating all the maximal independent sets. *SIAM Journal on Computing*, 6(3):505-517, 1977.

[Tro92] William T. Trotter. *Combinatorics and partially ordered sets*. Johns Hopkins Series in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 1992. Dimension theory.