{'fraction_non_alphanumeric': 0.04714578545251258, 'fraction_numerical': 0.0152183365426424, 'mean_word_length': 3.2042130919220058, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 42, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width

The linear induced matching width (LMIM-width) of a graph is a width parameter defined by using the notion of branch-decompositions of a set function on ternary trees. In this paper we study output-polynomial enumeration algorithms on graphs of bounded LMIM-width and graphs of bounded local LMIM-width. In particular, we show that all 1-minimal and all 1-maximal (\sigma,\rho)-dominating sets, and hence all minimal dominating sets, of graphs of bounded LMIM-width can be enumerated with polynomial (linear) delay using polynomial space. Furthermore, we show that all minimal dominating sets of a unit square graph can be enumerated in incremental polynomial time.


Introduction
Enumeration is at the heart of computer science and combinatorics. Enumeration algorithms for graphs and hypergraphs typically deal with listing all vertex subsets or edge subsets satisfying a given property. As the size of the output is often exponential in the size of the input, it is customary to measure the running time of enumeration algorithms in the size of the input plus the size of the output. If the running time of an algorithm is bounded by a polynomial in the size of the input plus the size of the output, then the algorithm is called output-polynomial. A large number of such algorithms have been given over the last 30 years; many of them solving problems on graphs and hypergraphs [9,10,11,14,20,21,22,24]. It is also possible to show that certain enumeration problems have no output-polynomial time algorithm unless P = NP [20,21,22].
Recently Kanté et al. showed that the famous longstanding open question whether there is an output-polynomial algorithm to enumerate all minimal transversals of a hypergraph, is equivalent to the question whether there is an output-polynomial algorithm to enumerate all minimal dominating sets of a graph [15]. Although the main question remains open, a large number of results have been obtained on graph classes. Output-polynomial algorithms to enumerate all minimal dominating sets exist for graphs of bounded treewidth and of bounded clique-width [8], interval graphs [9], strongly chordal graphs [9], planar graphs [11], degenerate graphs [11], split graphs [15], path graphs [16], permutation graphs [17], line graphs [12,16,19], chordal bipartite graphs [13], chordal graphs [18] and graphs of girth at least 7 [12].
In this paper, we extend the above results to graphs of bounded linear maximum induced matching width. Using the notion of branch-decompositions of a set function on ternary trees introduced by Robertson and Seymour, the notion of maximum induced matching width (MIM-width) was introduced by Vatshelle [26]. The linear maximum induced matching width (LMIM-width) of a graph is the linearized variant of the MIM-width like path-width is the linearized version of tree-width. (For definitions, see Section 2.) Belmonte and Vatshelle showed that several important graph classes, among them interval, circular-arc and permutation graphs, have bounded LMIM-width [3]. Polynomial-time algorithms solving optimization problems on such graph classes have been studied in [6,26].
In this paper, we study two ways of using bounded LMIM-width in enumeration algorithms. In Section 3 we study the enumeration problem corresponding to an extended and colored version of the well-known pσ, ρqdomination problem, asking to enumerate all 1-minimal and all 1-maximal Red pσ, ρq-dominating sets. This includes the enumeration of all minimal (total) dominating sets on graphs of bounded LMIM-width. We establish as our main result an enumeration algorithm with linear delay and polynomial space for this problem. Our algorithm uses the enumeration (and counting) of paths in directed acyclic graphs. In Section 4 we study the enumeration of all minimal dominating sets in unit square graphs. We first show that such graphs have bounded local LMIM-width. An hereditary graph class G has bounded local LMIM-width if there is a function f : N Ñ N such that the LMIM-width of every graph G in G is bounded by f pdiamq where diam is the diameter of G. The notion of bounded local width has been studied for several width notions and in particular in the area of Bidimensionality [1,2]. Then we show how to adapt the so-called flipping method developed by Golovach et al. [12] to enumerate all minimal dominating sets of a unit square graph in incremental polynomial time.

Definitions and preliminaries
Graphs. The power set of a set V is denoted by 2 V . For two sets A and B we let AzB be the set tx P A | x R Bu, and if X is a subset of a ground set V , we let s X be the set V zX. We often write x to denote the singleton set txu. We denote by N the set of positive or null integers, and let N˚be Nzt0u.
A graph G is a pair pV pGq, EpGqq with V pGq its set of vertices and EpGq its set of edges. An edge between two vertices x and y is denoted by xy (respectively yx). The subgraph of G induced by a subset X of its vertex set is denoted by GrXs, and we write GzX to denote the induced subgraph GrV pGqzXs. For F Ď EpGq, we denote by G´F the subgraph pV pGq, EpGqzF q. The set of vertices that is adjacent to x is denoted by N G pxq, and we let N G rxs be the set N G pxq Y txu. For U Ď V pGq, N G rU s " Y vPU N G rvs and N G pU q " N G rU szU . For a vertex x and a positive integer r, N r G rxs denotes the set of vertices at distance at most r from x. Clearly, N 1 G rxs " N G rxs. For two disjoint subsets A and B of V pGq, let GrA, Bs denote the graph with vertex set A Y B and the edge set tuv P EpGq | u P A, v P Bu. Clearly, GrA, Bs is a bipartite graph and tA, Bu is its bipartition. Recall that a set of edges M is an induced matching if end-vertices of distinct edges of M are different and not adjacent. We denote by mim G pA, Bq the size of a maximum induced matching in GrA, Bs.
Let G be a graph, and let Red, Blue Ď V pGq such that Red Y Blue " V pGq. We refer to the vertices of Red as the red vertices, the vertices of Blue as the blue vertices, and we say that G together with given sets Red and Blue is a colored graph. For simplicity, whenever we say that G is a colored graph, it is assumed that the sets Red and Blue are given. Notice that Red and Blue not necessarily disjoint. In particular, it can happen that Red " Blue " V pGq; a non-colored graph G can be seen as a colored graph with Red " Blue " V pGq. We deal with colored graphs because our algorithm for unit-square graphs requires as a subroutine an algorithm that takes as input a colored graph and enumerates all minimal subsets of red vertices that dominate the blue vertices.
A graph G is an (axis-parallel) unit square graph if it is an intersection graph of squares in the plane with their sides parallel to the coordinate axis. These graphs also are known as the graphs of cubicity 2. We use the following equivalent definition, see e.g. [7], in which each vertex v of G is represented by a point in R 2 . A graph G is a unit square graph if there is a function f : V pGq Ñ R 2 such that two vertices u, v P V pGq are adjacent in G if and only if }f puq´f pvq} 8 ă 1, where the norm }} 8 is the L 8 norm. For a vertex v P V pGq, we let x f pvq and y f pvq denote the x and y-coordinate of f pvq respectively. We say that the point px f pvq, y f pvqq represents v. The function f is called a realization of the unit square graph. It is straightforward to see that for any unit square graph G, there is its realization f : V pGq Ñ Q 2 . We always assume that a unit square graph is given with its realization. It is NP-hard to recognize unit square graphs [5]. We refer to the survey of Brandstädt, Le and Spinrad [4] for the definitions of all other graph classes mentioned in our paper.
Enumeration. Let D be a family of subsets of the vertex set of a given graph G on n vertices and m edges. An enumeration algorithm for D lists the elements of D without repetitions. The running time of an enumeration algorithm A is said to be output polynomial if there is a polynomial ppx, yq such that all the elements of D are listed in time bounded by pppn`mq, |D|q. Assume now that D 1 , . . . , D ℓ are the elements of D enumerated in the order in which they are generated by A. Let us denote by T pA, iq the time A requires until it outputs D i , also T pA, ℓ`1q is the time required by A until it stops. Let delaypA, 1q " T pA, 1q and delaypA, iq " T pA, iq´T pA, i´1q. The delay of A is maxtdelaypA, iqu. Algorithm A runs in incremental polynomial time if there is a polynomial ppx, iq such that delaypA, iq ď ppn`m, iq. Furthermore A is a polynomial delay algorithm if there is a polynomial ppxq such that the delay of A is at most ppn`mq. Finally A is a linear delay algorithm if delaypA, 1q is bounded by a polynomial in n`m and delaypA, iq is bounded by a linear function in n`m.
Linear maximum induced matching width. The notion of the maximum induced matching width was introduced by Vatshelle [26] (see also [3]). We will give the definition in terms of colored graphs and restrict ourselves to the case of linear maximum induced matching width. Let G be a colored n-vertex graph with n ě 2 and let x 1 , . . . , x n be a linear ordering of its vertex set. For each 1 ď i ď n, we let A i " tx 1 , x 2 , . . . x i u and s A i " tx i`1 , x i`2 , . . . x n u. The maximum induced matching width (MIMwidth for short) of x 1 , . . . , x n is Notice that if Red " Blue " V pGq, i.e., if G is an uncolored graph, the MIM-width of x 1 , . . . , x n is maxtmim G pA i , A i q|i P rn´1su. Consequently, The linear maximum induced matching width (LMIM-width) of G, denoted by lmimwpGq, is the minimum value of the MIM-width taken over all linear orderings of G.
Belmonte and Vatshelle [3] proved that several important graph classes have bounded linear maximum induced matching width. Theorem 1. For each of the following graph classes: interval graphs, permutation graphs, circular-arc graphs, circular permutation graphs, trapezoid graphs, convex graphs, and for fixed k, k-polygon graphs, Dilworth-k graphs and complements of k-degenerate graphs, there is a constant c such that lmimwpGq ď c for any graph G from the class. Moreover, the corresponding linear ordering of the vertices of MIM-width at most c can be found in polynomial time.
For example, the LMIM-width of an interval graph is 1 and the LMIMwidth of a circular-arc and of a permutation graph is at most 2. Before continuing, let us show that if a graph class G has LMIM-width c, then the graph class G 1 obtained from the graphs in G by partitioning their vertex set into Blue and Red also has LMIM-width c.
Proposition 2. If a colored graph G 1 is obtained from a non-colored graph G, then lmimwpG 1 q ď lmimwpGq.
We say that a graph class G has locally bounded LMIM-width if there is a function f : N Ñ N such that for any G P G and every u P V pGq, lmimwpGrN r G russq ď f prq for all r P N. pσ, ρq-domination. The pσ, ρq-dominating set notion was introduced by Telle and Proskurowski [25] as a generalization of dominating sets. Indeed, many NP-hard domination type problems such as the problems d-Dominating Set, Independent Dominating Set and Total Dominating Set are special cases of the pσ, ρq-Dominating Set Problem. See [6, Table 1] for more examples. For technical reasons, we introduce Red pσ, ρq-domination. Let σ and ρ be subsets of N. Throughout this paper it is assumed that σ and ρ are finite or co-finite. Notice that it can happen that σ is finite and ρ is co-finite and vice versa. We say that a subset D of V pGq pσ, ρq-dominates a vertex u if Let G be a colored graph. A set of vertices D Ď Red is a Red pσ, ρqdominating set if D pσ, ρq-dominates Blue. If Red " Blue " V pGq, then a Red pσ, ρq-dominating set is a pσ, ρq-dominating set.
Notice that if σ " N and ρ " N˚, then a set D Ď V pGq pσ, ρq-dominates a vertex u if u P D or u is adjacent to a vertex of D, i.e., the notion of pσ, ρqdomination coincides with the classical domination in this case. Whenever we consider this case, we simply write that a set D dominates a vertex or set and D is a (Red) dominating set omitting pσ, ρq.
A Red pσ, ρq-dominating set D of a graph G is said minimal if for any proper subset D 1 Ă D, D 1 is not a Red pσ, ρq-dominating set, and we say that D is 1-minimal if for each vertex x in D, Dzx is not a Red pσ, ρqdominating set. Respectively, a Red pσ, ρq-dominating set D is maximal if for any D 1 such that D Ă D 1 Ď Red, D 1 is not a Red pσ, ρq-dominating set and D is 1-maximal if for each vertex x in RedzD, D Y txu is not a Red pσ, ρq-dominating set. Clearly, every minimal or maximal Red pσ, ρqdominating set is 1-minimal or 1-maximal, respectively, but not the other way around because the converse is not true for arbitrary σ and ρ. Observe however that every (Red) 1-minimal (total) dominating set is also a (Red) minimal (total) dominating set. In Section 3 we enumerate only 1-minimal and 1-maximal Red pσ, ρq-dominating sets.
Because our aim is to enumerate 1-minimal or 1-maximal Red pσ, ρq-dominating sets, we need some certificate that a considered set is 1-minimal or 1-maximal respectively. Let D be a Red pσ, ρq-dominating set of a colored graph G. For a vertex u P D, we say that the vertex v P Blue is its certifying vertex (or a certificate) if v is not pσ, ρq-dominated by Dztuu, i.e., Respectively, for a vertex u P RedzD, the vertex v P Blue is its certifying vertex (or a certificate) if v is not pσ, ρq-dominated by D Y tuu.
Notice that because D is a Red pσ, ρq-dominating set, if v is a certificate for u, then v P N G rus. Observe also that a vertex can be a certificate for many vertices and it can be a certificate for itself. Notice that in the case of the classical domination, certificates are usually called privates because a vertex is always a certificate for exactly one vertex, including itself. It is straightforward to show the following.

Enumerations for graphs of bounded LMIM-width
In this section we prove the following. As a corollary of Theorems 1 and 4, and Proposition 2 we have the following.
Corollary 5. Let pσ, ρq be a pair of finite or co-finite subsets of N. Then, for every colored graph G in one of the following graph classes, we can count in polynomial time, and enumerate with linear delay all 1-minimal (or 1maximal) Red pσ, ρq-dominating sets of G: interval graphs, permutation graphs, circular-arc graphs, circular permutation graphs, trapezoid graphs, convex graphs, and for fixed k, k-polygon graphs, Dilworth-k graphs and complements of k-degenerate graphs.
The following corollary improves some known results in the enumeration of minimal transversals of some geometric hypergraphs (see e.g. [23]).

Corollary 6. For every hypergraph H being an interval hypergraph or a circular-arc hypergraph one can count in polynomial time, and enumerate with linear delay, all minimal transversals of H.
Proof. For any of the considered hypergraphs, its incidence graph is a subgraph of an interval or a circular-arc graph. If we color the vertices of the hypergraph in Red and the hyperedges in Blue, then X is a minimal transversal in the hypergraph if and only if it is a Red pN, N˚q-dominating set.
The remaining part of the section is devoted to the proof of Theorem 4. In Section 3.1 we give some technical definitions and lemmas that are important for the definition of the DAG whose maximal paths correspond to the desired sets. In Section 3.2 we define the DAG whose maximal paths correspond to the 1-minimal Red pσ, ρq-dominating sets and then show that it can be constructed in polynomial time. We also recall how to count in polynomial time, and enumerate with linear delay the maximal paths of a DAG. We then explain in Section 3.3 how the construction of Section 3.2 can be rewritten for 1-maximal Red pσ, ρq-dominating sets.

Technical Definitions
First because σ and ρ can be infinite, we need a finite way to check if a vertex is pσ, ρq-dominated. Let dpNq " 0. For every finite set µ Ď N, let dpµq :" 1`maxta | a P µu, and for every co-finite set µ Ď N, let dpµq :" 1`maxta | a P Nzµu. For finite or co-finite subsets σ and ρ of N, we let dpσ, ρq :" maxpdpσq, dpρqq. Given a subset D of Red, we can check if D is a Red pσ, ρq-dominating set by computing |D X N G pxq| up to dpσ, ρq for each vertex x in Blue [6]. We need the following properties of certificates.
Proof. Let v ‰ u be a certificate for u P D and let D 1 :" Dztuu.
The second claim can be proved by similar arguments.
By the definition of certificates, we have the next easy lemma.
Lemma 9. Let D be a Red pσ, ρq-dominating set of a colored graph G and let u P Red and v P Blue be distinct vertices of G. If u P D, then v is a certificate for u if and only if

is a certificate for itself if and only if it is blue and
Let d P N and let A be a subset of the vertex set of a colored graph G.
It is not hard to check that " d A is an equivalence relation and et us denote by necp" d A q the number of equivalence classes of " d A . Belmonte and Vatshelle [3] proved the following lemma restated in our setting.

Lemma 10 ([3]). Let d P N and let A be a subset of the vertex set of a colored
The next lemma is used to bound the number of information we have to store at each node of the DAG, which will consequently imply, combined with Lemma 10, that the size of the DAG is polynomial in the size of G.

and only if for every blue subset S of s
A there is C Ď S such that N pCq X pA X Redq " N pSq X pA X Redq and |C| ď k.

Constructing the DAG for 1-minimal sets
Throughout this section we let pσ, ρq be a fixed pair of finite or co-finite subsets of N and we let G be a fixed n-vertex colored graph with n ě 2. Let also x 1 , . . . , x n be a fixed linear ordering of the vertex set of G such that the MIM-width of x 1 , . . . , x n is bounded by a constant c. Furthermore, for all i P t1, 2, . . . , nu, we let We furthermore let d " dpσ, ρq.
We will follow the same idea as in [6] where a minimum (or a maximum) pσ, ρq-dominating set is computed, and we need for that to recall some definitions and lemmas (restated in our setting) proved in [6]. For every i P t1, . . . , nu and every subset X of One can also compute a data structure that given a set We will define a DAG, denoted by DAGpGq, the maximal paths of which correspond exactly to the 1-minimal Red pσ, ρq-dominating sets of G.
For 1 ď j ď n and C Ď A j X Blue (or C Ď s A j X Blue) we denote by SG j pCq (or by GG j pCq) the set X obtained from C if we we initially set X " C and recursively apply the following rule: let x be the greatest (or smallest) vertex in X such that N pXztxuqXp s A j XRedq " N pXqXp s A j XRedq (or N pXztxuq X pA j X Redq " N pXq X pA j X Redq) and set X " Xztxu. Notice that SG j pCq and GG j pCq are both uniquely determined, and both have sizes bounded by c from Lemma 11. Observe also that if C Ď A j XBlue (or C Ď s A j X Blue), then SG ℓ pC Y tx ℓ uq " SG ℓ pSG j pCq Y tx ℓ uq for all ℓ ą j (or GG ℓ pC Y tx ℓ uq " GG ℓ pGG j pCq Y tx ℓ uq for all ℓ ď j). The constructors SG j and GG j are used to canonically choose certificates in order to avoid redundancies.
Let 1 ď j ă n and let pR j , There is an ε-arc-2 from pR j , The nodes of DAGpGq. pR, ns is a node of DAGpGq whenever x i P Red, C " SG i pCq and C 1 " GG i pC 1 q. We call i the index of pR, R 1 , C, C 1 , iq. Finally s " pH, H, H, H, 0q is the source node and t " pH, H, H, H, n`1q is the terminal node of DAGpGq.
The arcs of DAGpGq. There is an arc from the node pR 0 , There is an arc from the source node to a node pR, if (x j P Blue and |N px j qXR 1 | P σ´) then C " SG j pS Ytx j uq, otherwise C " SG j pSq, and (S3) either (N px j q X pC 1 Y Cq ‰ H) or (x j P Blue and |N px j q X R 1 | P σ˚).
There is an arc from a node pR, R 1 , C, C 1 , jq to the terminal node if (T1) |N pxq X R| P ρ for each x P s A j`1 X Blue, and (T2) C 1 " GG j ptx P s A j X Blue | N pxq X pA j X Redq ‰ H and |N pxq X R| P ρ´uq.
Lemma 13. DAGpGq is a DAG and can be constructed in time Opn c¨d q.
Proof. An arc is always oriented from a node pR, R 1 , C, C 1 , jq to pR,R 1 ,Ĉ,Ĉ 1 , jp q with p ě 1. Therefore, we cannot create circuits, i.e., DAGpGq is a DAG. For each index 1 ď i ď n and each node pR, R 1 , C, C 1 , iq of index i we know by [3, Lemma 1] that |C|, |C 1 | ď c. Hence, the number of nodes of DAGpGq of index i is Opn c¨d q since necp" d A i q ď n d¨c by Lemma 10. Now, constructing the arcs from the source node can be done in Opn c¨d q time since it suffices to check for each node pR, R 1 , C, C 1 , jq if conditions (S1)-(S3) are satisfied, which can be done trivially in polynomial time with the help of Lemma 12. Similarly, since the conditions (T1) and (T2) can be checked in polynomial time, the incoming arcs to the terminal node can be constructed in Opn c¨d q time. Now, to construct an arc from pR 0 , R 1 0 , C 0 , C 1 0 , jq to pR p , R 1 p , C p , C 1 p , j`pq we do as follows. For 0 ď i ď p´1 we let F i be a queue and we put i´1 , C i´1 , C 1 i´1 q to pR, R 1 , C, C 1 q, then put pR, R 1 , C, C 1 q in F i . Now, by the definition of an arc in DAGpGq there is an arc from pR 0 , R 1 0 , C 0 , C 1 0 , jq to pR p , R 1 p , C p , C 1 p , j`pq if and only if there is one pR p´1 , R 1 p´1 , C p´1 , C 1 p´1 q in F p´1 such that there is an ε-arc-2 from pR p´1 , R 1 p´1 , C p´1 , C 1 p´1 q to pR p , R 1 p , C p , C 1 p , j`pq. Now, the size of each F i is bounded by Opn c¨d q, and since the conditions of ε-arc-1 and ε-arc-2 can be checked in Opn c¨d q time with the help of Lemma 12, we can check if there is an arc between two nodes in time Opn c¨d q.
We now prove that there is a one-to-one correspondence between the maximal paths of G and the 1-minimal Red pσ, ρq-dominating sets of G. If P " ps, v 1 , v 2 , . . . , v p , tq is a path in DAGpGq, then the trace of P , denoted by tracepP q, is defined as tx j 1 , x j 2 , . . . , x jp u where for all i P t1, 2, . . . , pu, j i is the index of the node v i .
The following two lemmas are implied by the definition of the d-neighbor equivalence and Lemma 8.
Proof. Let P " ps, v 1 , . . . , v k , tq and tracepP q " tx j 1 , . . . , x j k u. We will first prove by induction that for each 1 ď i ď k, the set D i " tx j 1 , . . . , x j i u satisfies the following properties (with (v) C j i " SG j i pS i q, where S i is the set of vertices in A j i X Blue that are certificates and have a neighbor in s A j i X Red; By the definition of a node in DAGpGq, the property (i) is true for all 1 ď i ď k. So, let us prove the properties (ii)-(v). By the definition of the arcs from the source node, we can easily check that the properties (ii)-(v) are all verified for i " 1. So, let us assume now that they are true for all i ă ℓ ď k and let us prove it for ℓ.
If there is an arc from v ℓ´1 to v ℓ , then there should exist pR s , R 1 s , C s , C 1 s q for j ℓ´1`1 ď s ď j ℓ´1 such that there is an ε-arc-1 from pR s´1 , R 1 s´1 , C s´1 , C 1 s´1 q to pR s , R 1 s , C s , C 1 s q for each j ℓ´1`1 ď s ď j ℓ´1 , and there is an ε-arc-2 from pR j ℓ´1 , R 1 j ℓ´1 , C j ℓ´1 , C 1 j ℓ´1 q to pR j ℓ , R 1 j ℓ , C j ℓ , C 1 j ℓ q. By the conditions (1.1) and (2.1) we can conclude that D j ℓ " d As R s for all j ℓ´1`1 ď s ď j ℓ´1 by the condition (1.1) and R 1 j ℓ Y tx j ℓ u by (2.1) we can conclude with inductive hypothesis, Lemmas 14 and 15, and the conditions (1.2) and (2.1) that for each j ℓ´1`1 ď s ď j ℓ whenever x s P Blue it is pσ, ρq-dominated by D j ℓ Y R 1 j ℓ , thus proving (iii).
In order to check (iv) and (v), we let D s " D j ℓ´1 for each j ℓ´1`1 ď s ď j ℓ´1 . Then, for each j ℓ´1`1 ď s ď j ℓ , the following easy facts can be derived from Lemmas 14 and 15, the definition of the d-neighbor equivalence and the fact that D s X R 1 s " H.
1. For each v P s A s X Blue, we have pD s Y R 1 s q pσ´, ρ´q-dominates tvu if and only if pR s Y R 1 s q pσ´, ρ´q-dominates tvu; and |N pvq X D s | ‰ 0 if and only if |N pvq X R s | ‰ 0.

For each
4. Each u P D s´1 either has a certificate in A s w.r.t. D s or is adjacent to a vertex from C 1 s . Indeed, either it has by induction a certificate v from A s´1 w.r.t. D s´1 and by (2) and Lemma 9 the vertex v is still a certificate for u w.r.t. D s , or u is adjacent to some vertex in C 1 s´1 and then by induction and the conditions (1.2) and (2.2) either it is adjacent to some vertex in C 1 s or it is adjacent to x s which is pσ´, ρ´q-dominated by D s Y R 1 s following fact 3.
From the facts 1. and 2. we can conclude that pD s Y R 1 s q pσ´, ρ´qdominates C s for all j ℓ´1`1 ď s ď j ℓ . Hence, pD j ℓ YR 1 j ℓ q pσ´, ρ´q-dominates C j ℓ . Moreover, from the fact 4. we know that each u P D j ℓ´1 is either adjacent to a vertex in C 1 j ℓ or has a certificate w.r.t. D j ℓ in A j ℓ X Blue. In order to prove that (iv) is satisfied it remains then to check that x j ℓ has a certificate in A j ℓ X Blue or has a neighbor in C 1 ℓ . But this is guaranteed with the existence of the arc v ℓ´1 to v ℓ by the conditions (1.2.a), (2.2.a), (2.3), and the properties (iv)-(v) by inductive hypothesis.
In order to check the condition (v) it is sufficient to notice that whenever x s is pσ´, ρ´q-dominated by pD s Y R 1 s q for each j ℓ´1`1 ď s ď j ℓ , by the condition (1.2.a) and (2.2.a) C s " SG s pC s´1 Y x s q, and this guarantees by inductive hypothesis, the fact 2. and Lemma 9 that C s is exactly SG s pS s q where S s is the set of vertices in A s X Blue that are certificates and have a neighbor in s A s . To end the proof we need to prove that whenever tracepP q " tracepP 1 q for any other path P 1 from the source node to the terminal node, then P " P 1 . For that we prove by induction that C 1 j i " GG j i pS 1 i q where S 1 i is the set of vertices in s A j i X Blue that are pσ´, ρ´q-dominated by D j i Y R 1 j i and have a neighbor in A j i XRed. By the condition (T2) in the definition of an arc to the terminal node this is satisfied by C 1 j k . So, if we assume that C 1 j i " GG j i pS 1 i q for all ℓ ă i ď k, then as for the condition (v) the inductive hypothesis, the fact 2. and Lemma 9 guarantees that C 1 j ℓ is exactly GG j ℓ pS 1 ℓ q.
So now for each i the sets C j i and C 1 j i are uniquely determined by tracepP q, which means that whenever tracepP q " tracepP 1 q because " d A is an equivalence relation we should conclude that P " P 1 .
The following lemma tells that to every 1-minimal Red pσ, ρq-dominating set corresponds a maximal path in DAGpGq.
Proof. Let D " tx j 1 , . . . , x j k u such that j 1 ă j 2 ă¨¨¨ă j k . For each i P t1, . . . , ku, we let D i " tx j 1 , . . . , x j i u. Let also R j i P LR j i be such that For each i we let C j i " SG j i pS i q where S i is the set of vertices in A j i X Blue that are certificates and have a neighbor in s A j i XRed and similarly let C 1 We first observe that there is an arc from the source node s to v 1 . Indeed, by the definition of pσ, ρq-dominates A j 1 , and by the choices of C j i and C 1 j i the condition (S2) is satisfied and since x j 1 has a certificate w.r.t. D, the condition (S3) is satisfied. For similar reasons one can prove that there is an arc from v k to the terminal node t.
We now claim that there is an arc from v i to v i`1 for 1 ď i ă k. For each j i ă s ă j i`1 , we let pR s , R 1 s , C s , C 1 s q be such that R s " d It is straightforward to prove by induction on j i`1´ji that there exists an ε-arc-1 from pR s´1 , R 1 s´1 , C s´1 , C 1 s´1 q to pR s , R 1 s , C s , C 1 s q for each j i ă s ă j i`1 and there is an ε-arc-2 from pR j i`1´1 , R 1 j i`1´1 , C j i`1´1 , C 1 j i`1´1 q to pR j i`1 , R 1 j i`1 , C j i`1 , C 1 j i`1 q. By Lemmas 16 and 17 we can state the following.
Proposition 18. Let P be the set of paths in DAGpGq from the source node to the terminal node. The mapping which associates with every P P P tracepP q is a one-to-one correspondence with the set of 1-minimal Red pσ, ρqdominating sets.
By Proposition 18 it suffices to count and enumerate the traces of the maximal paths in DAGpGq. We will now explain how to count and then use the counting to enumerate the traces of these paths in DAGpGq. We start from a topological ordering of DAGpGq, say s " v 1 , v 2 , . . . , v m " t. Since DAGpGq is a DAG, any arc is of the form pv i , v j q with i ă j. The counting will follow this topological ordering. We initially set N ppvq "´1 for all nodes v ‰ t and we set N ppv m q " 1. For each j ă m we let Fact 19. One can compute the values of N ppv j q for all j P t1, 2, . . . , mu in time Opn c¨d q.
Proof. By induction on j. By definition N ppvq can be computed in time Op1q for all v that have exactly one outgoing arc, which enters t. For every j ă m, in order to compute N ppv j q we first set a counter nb to 0, and add N ppv ℓ q to nb whenever pv j , v ℓ q P EpDAGpGqq and N ppv ℓ q ‰´1. We finally set N ppv j q to nb. The correctness of the computation of N ppv j q follows from the definition. Since the degree of a node is bounded by Opn c¨d q, we can update nb in time Opn c¨d q. Now since the number of nodes and of arcs is bounded by Opn c¨d q, we obtain the claimed running time.
For 1 ď j ď m, we let S j " tP | P is a path starting at v j and ending at tu. One can prove easily by induction the following.
tv j`P | P P S ℓ u for each 1 ď j ď m.
The following follows directly from the definition of N ppv j q and Lemma 20. Proof. We first construct the DAG DAGpGq and by Lemma 13 this can be done in time Opn c¨d q. By Proposition 18 the mapping which associates with every path P P S 1 its trace tracepP q is a one-to-one correspondence between S 1 and all the 1-minimal Red pσ, ρq-dominating set in G. So, it is enough to determine the size of S 1 . By Lemma 21, |S 1 | " N ppsq and since by Fact 19 we can compute in time Opn c¨d q all the values N ppv j q for all 1 ď j ď m, we conclude that one can compute in time Opn c¨d q the number of 1-minimal Red pσ, ρq-dominating sets in G.
We now turn to the enumeration of the 1-minimal Red pσ, ρq-dominating sets. For each node v in DAGpGq of index j we denote by vertpvq the vertex x j of G. The algorithm is depicted in Figures 1 and 2. The algorithm consists in enumerating the paths in S 1 in a Depth-First Search manner.
Algorithm EnumMinDompDAGpGqq 1. Remove all nodes v such that N ppvq "´1 2. for each ps, v i q P EpDAGpGqq 3. EnumPathpDAGpGq, tvertpv i qu, v i q 4. end for Figure 1: The enumeration of 1-minimal Red pσ, ρq-dominating sets Proof. First notice that after removing all the nodes v such that N ppvq "´1, every remaining node is in a path from the source node to the terminal node. Now, it is easy to prove by induction using Lemmas 20 and 21 that the algorithm EnumPathpDAGpGq, S, v i q uses Opn c¨d q space and enumerates the set tS Y P | P P S i u, the delay between two consecutive outputs P 1 and P 2 bounded by Op|P 2 zP 1 |q. In fact if before calling EnumPath we order the out-neighbors of each node following their distances to the terminal node and uses this ordering in the recursive calls we guarantee that the time between the output of P and the next output Q is bounded by Op|Q|q. Therefore, the algorithm EnumMinDompDAGpGqq enumerates, with same delay as EnumPath the set of 1-minimal Red pσ, ρq-dominating sets and uses Opn c¨d q space.

Maximal sets
We now explain how to construct the DAG DAGM pGq so that the maximal paths from the source node to the terminal node corresponds to the 1-maximal Red pσ, ρq-dominating sets, and conversely each 1-maximal Red pσ, ρq-dominating set corresponds to such a path. The difference with the case of 1-minimal pσ, ρq-dominating set is that now we have to ensure that x j has a certificate when x j is not included in a partial solution.
The nodes of DAGM pGq. pR, R 1 , C, C 1 , iq P LR iˆL Rīˆ2 A i XBlue2 s A i XBlueˆr ns is a node of DAGM pGq whenever x i P Red, C " SG i pCq and C 1 " GG i pC 1 q. We call i the index of pR, R 1 , C, C 1 , iq. Finally s " pH, H, H, H, 0q is the source node and t " pH, H, H, H, n`1q is the terminal node of DAGpGq.
The arcs of DAGpGq There is an arc from pR 0 , pR 1 p Y tx j`p uq, x j`p P Red, and (2.1) if x j`p P Blue, then |N px j`p q X pR p´1 Y R 1 p q| P σ, (2.2) if (x j`p R Blue or (x j`p P Blue and |N px j`p q X pR p´1 Y R 1 p q| R σ`)), then (C p " SG p pC p´1 q and C 1 p´1 " GG p´1 pC 1 p q), otherwise we should have (|N px j`p q X pR p´1 Y R 1 p q| P σ`) and We now define arcs from the source node. There is an arc from the source node to a node pR, R 1 , C, C 1 , jq if (S " tx P pA j X Blueqztx j u | N pxq X p s A j X Redq ‰ H and |N pxq X ptx j u Y R 1 q| P ρ`u) (S1) tx j u " d A j R and ptx j u Y R 1 q pσ, ρq-dominates A j X Blue, (S2) if (x j P Blue and |N px j qXR 1 | P σ`) then C " SG j pS Ytx j uq, otherwise C " SG j pSq, and (S3) for each red vertex x P A j ztx j u, either (N pxq X pC 1 Y Cq ‰ H) or (x P Blue and |N pxq X pR 1 Y Rq| P ρ˚).
We finally define the arcs to the terminal node. There is an arc from a node pR, R 1 , C, C 1 , jq to the terminal node if (T1) |N pxq X pR Y R 1 q| P ρ for each x P s A j`1 X Blue, and (T2) C 1 " GG j ptx P s A j X Blue | N pxq X pA j X Redq ‰ H and |N pxq X R| P ρ`uq, DAGM pGq is clearly a DAG, and as for DAGpGq one can construct it in time Opn c¨d q. Similarly, one can observe that if P :" ps, v 1 , . . . , v k , tq is a maximal path from the source node to the terminal node, then if we let (iv) Each u P A j i zD i is either adjacent to a vertex from C 1 j i , or has a certificate in A j i X Blue.
(v) C j i " SG j i pS i q, where S i is the set of vertices in A j i X Blue that are certificates and have a neighbor in s A j i X Red; (vi) C 1 j i " GG j i pS 1 i q where S 1 i is the set of vertices in s A j i X Blue that are certificates and have a neighbor in A j i X Red.
Hence, we can prove counterparts to Lemmas 16 and 17 and deduce the following theorem from Section 3.2.
Theorem 24. The set of 1-maximal Red pσ, ρq-dominating sets in G can be enumerated with linear delay and with polynomial space. We can moreover count in time Opn c¨d q the number of 1-maximal Red pσ, ρq-dominating sets in G.

Enumeration of minimal dominating sets for unit square graphs
In this section we prove that all minimal dominating sets of a unit square graph can be enumerated in incremental polynomial time. In Section 4.1 we show that the class of unit square graphs has locally bounded LMIM-width. In Section 4.2 we use this property and Theorem 4, to obtain an enumeration algorithm for minimal dominating sets. To do it, we use the flipping method proposed by Golovach, Heggernes, Kratsch and Villanger in [12].

Local LMIM-width of unit square graphs
First, we introduce some additional notations. For x, y P R such that x ď y, rx, ys " tz P R | x ď z ď yu. Let G be a unit square graph and suppose that f : V pGq Ñ Q 2 is a realization of G. (See Section 2 for more details on the point model of unit square graphs used in our paper.) For a vertex v P V pGq, fracpvq " x f pxq´tx f pvqu is the fractional part of the x-coordinate of the point representing v.
Lemma 25. Let G be a unit square graph with a realization f such that for every v P V pGq the point f pvq belongs to r1, wsˆr1, hs, where h, w P N. If for x P r1, ws, A " tv P V pGq | x f " xu is a non-empty proper subset of V pGq, then mim G pA, Aq ď h. We claim that a i b i P M for i P t1, . . . , ku. To obtain a contradiction, suppose that there is a i that is not adjacent to b i and choose the minimum index i for which it holds. Then a i b j P M and b i a s P M for some j, s ą i. If b i is adjacent to a s but not a i , we must have |y f pb i q´y f pa i q| ě 1 and |y f pb i q´y f pa s q| ă 1. Since y f pa s q ě y f pa i q, y f pb i q ě y f pa i q`1. But as y f pb j q ě y f pb i q ě y f pa i q`1, b j and a i cannot be adjacent after all; a contradiction. Now we show that y f pa i q ě y f pb i´1 q`1 and y f pb i q ě y f pa i´1 q`1 for i P t2, . . . , ku. Because a i´1 b i´1 P M , |y f pa i´1 q´y f pb i´1 q| ă 1. As a i´1 b i , a i b i´1 R EpGq, |y f pa i´1 q´y f pb i q| ě 1 and |y f pa i q´y f pb i´1 q| ě 1.
We have that y f pa i q ě y f pb i´1 q`1 and y f pb i q ě y f pa i´1 q`1, because y f pa i q ě y f pa i´1 q and y f pb i q ě y f pb i´1 q.
Next, we claim that y f pa i q, y f pb i q ě i. Clearly, y f pa 1 q, y f pb 1 q ě 1. Because y f pa i q ě y f pb i´1 q`1 and y f pb i q ě y f pa i´1 q`1 for i P t2, . . . , ku, we have that claim holds for all i P t1, . . . , ku by induction.
Because k ď y f pa k q ď h, we conclude that mim G pA, s Aq " k ď h.
Lemma 26. Let G be a unit square graph with a realization f such that for every v P V pGq the point f pvq belongs to r1, wsˆr1, hs, where h, w P N. Then lmimwpGq ď 2hw. Moreover, a linear ordering of vertices of MIM-width at most 2hw can be constructed in polynomial time.
Proof. Let v 1 , . . . , v n be the vertices of G ordered by increasing frac-value, i.e., fracpv i q ď fracpv j q if i ď j. We show that this is an ordering of MIMwidth at most 2hw.
For contradiction, assume that for some i P t1, . . . , n´1u, mim G pA, s Aq ě 2hw`1 where A " tv 1 , . . . , v i u, i.e., the graph GrA, s As has an induced matching M of size 2hw`1. Let V pM q denote the set of the end-vertices of the edges of M . By the pigeonhole principle, for some positive integer p ď w there are at least 2h`1 vertices v P V pM q X A so that tx f pvqu " p. Denote this subset of A X V pM q by C A , and denote by C B the vertices of V pM qzA adjacent to C A . Let t " maxtfracpvq | v P Au, and observe that tv | fracpvq ă tu Ă A and tv | fracpvq ą tu X A " H. We now partition C A into two parts C ăt A " tv P C A | fracpvq ă tu and C "t A " tv P C A | fracpvq " tu and argue that neither of these parts can be of size more than h, contradicting that |C A | ě 2h`1.
We first show that |C "t A | ď h. For each v P C "t A , tx f pvqu " p and fracpvq " t. Hence, x f pvq " p`t for all v P C "t A . By Lemma 25, the size of the maximum induced matching in GrC "t A , C B s is at most h and this implies that |C "t A | ď h. To show that also |C ăt A | ď h, we will show that for the sake of the induced matching, all the x-coordinates of the vertices v of C ăt A might as well have fracpvq " 0, and therefore we can apply Lemma 25.
Let v P C ăt A . Then we construct a new vertex v 1 represented by the point ptx f pvqu, y f pvqq. We will now show that v 1 is adjacent to a vertex u P C B if and only if v is adjacent to u. As the y-coordinates of v and v 1 are the same, we only need to prove that |x f pvq´x f puq| ă 1 if and only if |tx f pvqu´x f puq| ă 1.
Suppose that v is adjacent to u but v 1 is not. Because x f pvq ě tx f pvqu, we have that tx f pvqu`1 ě x f puq ą x f pvq`1. However, that means fracpuq ď fracpvq ă t, which implies that u P A contradicting u P C B . Similarly, suppose v 1 is adjacent to u but v is not. Now tx f pvqu´1 ă x f puq ď x f pvq´1, which again implies that fracpuq ď fracpvq ă t, contradicting that u is in C B .
Consider S " tv 1 | v P C ăt A u, where each v 1 is represented by the point ptx f pvqu, y f pvqq " pp, y f pvqq. Because each v 1 P S is adjacent to u P C B if and only if v is adjacent to u, by Lemma 25, |C ăt A | " |S| ď h. It remains to show that the ordering of V pGq can be constructed in polynomial time. Clearly, the ordering can be done in time Opn log nq if we assume that we can compute fracpvq and compare the frac-values of two vertices in time Op1q. Otherwise, if the table of the values f : V pGq Ñ Q 2 is given in the input, we still can produce the ordering in polynomial time.
Now we are ready to show that the class of unit square graphs has locally bounded LMIM-width.
Theorem 27. For a unit square graph G, u P V pGq and a positive integer r, lmimwpGrN r G russq " Opr 2 q. Moreover, if a realization f : V pGq Ñ Q 2 of G is given, then a linear ordering of the vertices of MIM-width Opr 2 q can be constructed in polynomial time.
Proof. Let f be a realization of G. Without loss of generality we may assume that mintx f pvq | v P N r G rusu " minty f pvq | v P N r G rusu " 1. Otherwise, we can shift the points representing vertices. For any v P N r G rus, |x f puqx f pvq| ď r and |y f puq´y f pvq| ď r. We obtain that f pvq P r1, 2r`1sr 1, 2r`1s. By Lemma 26, lmimwpGrN r G russq " Opr 2 q and the corresponding ordering of the vertices can be constructed in polynomial time.

Enumeration by flipping for graphs of locally bounded LMIM-width
We use a variant of the flipping method proposed by Golovach, Heggernes, Kratsch and Villanger in [12]. Given a minimal dominating set D˚, the flipping operation replaces an isolated vertex of GrD˚s with its neighbor outside of D˚, and, if necessary, adds or deletes some vertices to obtain new minimal dominating sets D, such that GrDs has more edges compared to GrD˚s. The enumeration algorithm starts with enumerating all maximal independent sets of the input graph G using the algorithm of Johnson, Papadimitriou, and Yannakakis [14], which gives the initial minimal dominating sets. Then the flipping operation is applied to every appropriate minimal dominating set found, to find new minimal dominating sets inducing subgraphs with more edges. Let G be a graph. Let also D Ď V pGq. For u P D, C D rus " tv P V pGq | v P N G ruszN G rDztvusu and C D puq " tv P V pGq | v P N G puqzN G rDztvusu " C D rusztuu. Observe that if D is a minimal dominating set, then C D puq is the set of certificates for a vertex u P D.
Let us describe the variant of the flipping operation from [12], that we use. Let G be the input graph; we fix an (arbitrary) order of its vertices: v 1 , . . . , v n . Suppose that D 1 is a dominating set of G. We say that the minimal dominating set D is obtained from D 1 by greedy removal of vertices (with respect to order v 1 , . . . , v n ) if we initially let D " D 1 , and then recursively apply the following rule: If D is not minimal, then find a vertex v i with the smallest index i such that Dztv i u is a dominating set in G, and set D " Dztv i u. Clearly, when we apply this rule, we never remove vertices of D 1 that have certificates. Whenever greedy removal of vertices of a dominating set is performed, it is done with respect to this ordering.
Let D be a minimal dominating set of G such that GrDs has at least one edge uw. Then the vertex u P D is dominated by the vertex w P D. Therefore, C D rus " C D puq ‰ H. Let X be an non-empty inclusion-maximal independent set such that X Ď C D puq. Consider the set D 1 " pDztuuq Y X. Notice that D 1 is a dominating set in G, since all vertices of C D puq are dominated by X by the maximality of X and u is dominated by w, but D 1 is not necessarily minimal, because it can happen that X dominates all the certificates of some vertex of Dztuu. We apply greedy removal of vertices to D 1 to obtain a minimal dominating set. Let Z be the set of vertices that are removed by this to ensure minimality. Observe that X X Z " H and u R Z by the definition of these sets; in fact there is no edge between a vertex of X and a vertex of Z. Finally, let D˚" ppDztuuq Y XqzZ.
It is important to notice that |EpGrD˚sq| ă |EpGrDsq|. Indeed, to construct D˚, we remove the endpoint u of the edge uw P EpGrDsq and, therefore, reduce the number of edges. Then we add X but these vertices form an independent set in G and, because they are certificates for u with respect to D, they are not adjacent to any vertex of Dztuu. Therefore, |EpGrD˚sq| ď |EpGrD 1 sq| ă |EpGrDsq|.
The flipping operation is exactly the reverse of how we generated Df rom D; i.e., it replaces a non-empty independent set X in GrD˚s such that X Ď GrD˚sXN G puq for a vertex u R D˚with their neighbor u in G to obtain D. In particular, we are interested in all minimal dominating sets D that can be generated from D˚in this way. Given D and D˚as defined above, we say that D˚is a parent of D with respect to flipping u and X. We say that D˚is a parent of D if there is a vertex u P V pGq and an independent set X Ď N G puq such that D˚is a parent with respect to flipping u and X. It is important to note that each minimal dominating set D such that EpGrDsq ‰ H has a unique parent with respect to flipping of any u P D X N G rDztuus and a maximal independent set X Ď C D puq, as Z is lexicographically first sets selected by a greedy algorithm. Similarly, we say that D is a child of D( with respect to flipping u and X) if D˚is the parent of D (with respect to flipping u and X).
The proof of the following lemma is implicit in [12].
Lemma 28 ( [12]). Suppose that for a graph G, all independent sets X Ď N G puq for a vertex u can be enumerated in polynomial time. Suppose also that there is an enumeration algorithm A that, given a minimal dominating set D˚of a graph G such that GrD˚s has an isolated vertex, a vertex u P V pGqzD˚and a non-empty independent set X of GrD˚s such that X Ď D˚XN G puq, generates with polynomial delay a family of minimal dominating sets D with the property that D contains all minimal dominating sets D that are children of D˚with respect to flipping u and X. Then all minimal dominating sets of G can be enumerated in incremental polynomial time.
To obtain our main result, we will show that there is indeed an algorithm as algorithm A described in the statement of Lemma 28 when the input graph G is a unit square graph. We show that we can construct A by reduction to the enumeration of minimal Red dominating set in an auxiliary colored induced subgraph of GrN 3 G russ. Let D˚be a minimal dominating set of a graph G such that GrD˚s has an isolated vertex. Let also u P V pGqzD˚and X is a non-empty independent set of GrD˚s such that X Ď D˚X N G puq. Consider the set D 1 " pDzXq Y tuu. Denote by Blue the set of vertices that are not dominated by D 1 . Notice that Blue Ď N G pXqzN G rus. Therefore, Blue Ď N 2 G rus. Let Red " N G pBlueqzN G rXs. Clearly, Red Ď N 3 G rus. We construct the colored graph H " GrRed Y Blues. Let A 1 be an algorithm that enumerates minimal Red dominating sets in H. Assume that if Blue " H, then A 1 returns H as the unique Red dominating set. We construct A as follows.
Step 1. If A 1 returns an empty list of sets, then A returns an empty list as well.
Step 2. For each Red dominating set R of H, consider D 2 " D 1 Y R and construct a minimal dominating set D from D 2 by greedy removal.
Lemma 29. If A 1 lists all minimal Red dominating sets with polynomial delay, then A generates with polynomial delay a family of minimal dominating sets D with the property that D contains all minimal dominating sets D that are children of D˚with respect to flipping u and X.
Proof. First, we show that A produces pairwise distinct minimal dominating sets of G. Let R be a Red dominating set of H. The set D 1 " pDzXq Y tuu dominates all vertices of G except the vertices of Blue. Since R dominates Blue, D 2 is a dominating set of G and, therefore, D˚obtained from D 2 by the greedy removal is a minimal dominating set. To see that all generated sets are distinct, observe that every vertex of R has its certificate in B. Therefore, the greedy removal never deletes vertices of R. Since all sets R generated by A 1 are pairwise distinct, the claim follows. Let D be a child of D˚with respect to flipping u and X. Then D " ppD˚Y tuuqzXq Y Z. Recall that u R Z, X X Z " H and the vertices of Z are not adjacent to the vertices of X by the definition of X and Z. Hence, Z X Blue " H. Because D is minimal, each vertex of Z has a certificate. As only the vertices of Blue are not dominated by pD˚Y tuuqzX, each vertex of Z has its certificate in Blue. It remains to observe that Z dominates Blue, to see that Z is a minimal Red dominating set of H. Because A 1 generates all minimal Red dominating sets, we have that D P D. Now we are ready to prove the main result of the section.
Theorem 30. For a unit square graph G given with its realization f , all minimal dominating sets of G can be enumerated in incremental polynomial time.
Proof. It is straightforward to observe that for a vertex u of a unit square graph G, any independent set X Ď N G puq has at most 4 vertices. Hence, all independent sets X Ď N G puq for a vertex u can be enumerated in polynomial time. By combining Theorems 4 and 27, and Lemmas 28 and 29, we obtain the claim.