Output-Polynomial Enumeration on Graphs of
Bounded (Local) Linear MIM-Width˚

arXiv:1509.03753v2 [cs.DS] 15 Sep 2015

Petr A. Golovach:

Pinar Heggernes:

Mamadou Moustapha Kanté;
Sigve H. Sæther:

Dieter Kratsch§

Yngve Villanger:

February 19, 2018

Abstract
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 outputpolynomial 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 pσ, ρq-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.

1

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
˚
The research leading to these results has received funding from the European Research
Council under the European Union’s Seventh Framework Programme (FP/2007-2013) /
ERC Grant Agreement n. 267959.
:
Department of Informatics, University of Bergen, Norway
;
Clermont-Université, Université Blaise Pascal, LIMOS, CNRS, Aubiére, France
§
Université de Lorraine, LITA, Metz, France

1

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 deﬁnitions, 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 ﬁrst 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 ﬂipping method developed
by Golovach et al. [12] to enumerate all minimal dominating sets of a unit
square graph in incremental polynomial time.
2

2

Definitions and preliminaries

Graphs. The power set of a set V is denoted by 2V . 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
s be the set V zX. We often write x to denote the singleton
set V , we let X
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
NG pxq, and we let NG rxs be the set NG pxq Y txu. For U Ď V pGq, NG rU s “
YvPU NG rvs and NG pU q “ NG rU szU . For a vertex x and a positive integer
r, NGr rxs denotes the set of vertices at distance at most r from x. Clearly,
NG1 rxs “ NG 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 diﬀerent and not adjacent. We denote by mimG 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 deﬁnition, see e.g. [7], in which each vertex v of
G is represented by a point in R2 . A graph G is a unit square graph if
there is a function f : V pGq Ñ R2 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 L8 norm. For a vertex v P V pGq, we let xf pvq and yf pvq denote the x
and y-coordinate of f pvq respectively. We say that the point pxf pvq, yf 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
3

realization f : V pGq Ñ Q2 . 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 deﬁnitions
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 D1 , . . . , 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 Di , 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 deﬁnition 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 x1 , . . . , xn be a linear ordering
of its vertex set. For each 1 ď i ď n, we let Ai “ tx1 , x2 , . . . xi u and
si “ txi`1 , xi`2 , . . . xn u. The maximum induced matching width (MIMA
width for short) of x1 , . . . , xn is
si X Blueq, mimG pAi X Blue, A
si X Redqu.
max maxtmimG pAi X Red, A

1ďiďn´1

Notice that if Red “ Blue “ V pGq, i.e., if G is an uncolored graph, the
MIM-width of x1 , . . . , xn is maxtmimG pAi , Ai 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.
4

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 G1 is obtained from a non-colored graph
G, then lmimwpG1 q ď lmimwpGq.
Proof. Let A Ă V pGq. For the colored graph G1 , maxtmimG1 pA, Aq ď
mimG1 pAXRed, AXBlueq, mimG1 pAXBlue, AXRedqu. Because mimG1 pAX
Red, AXBlueq “ mimG pAXRed, AXBlueq ď mimG pA, Aq and mimG1 pAX
Blue, AXRedq “ mimG pAXBlue, AXRedq ď mimG pA, Aq, mimG1 pA, Aq ď
mimG pA, Aq and the claim follows.
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,
lmimwpGrNGr 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 dDominating 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 ﬁnite or co-ﬁnite. Notice that it can happen that σ is ﬁnite and ρ
is co-ﬁnite and vice versa. We say that a subset D of V pGq pσ, ρq-dominates
a vertex u if

|NG puq X D| P

#

σ
ρ

if u P D,
if u R D.

It is said that D pσ, ρq-dominates U Ď V pGq if D pσ, ρq-dominates every
vertex of U .
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
5

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 certiﬁcate 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.,

|NG pvq X pDztuuq| R

#

if v P pDztuuq X Blue,
if v P BluezpDztuuq.

σ
ρ

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 certiﬁcate
for u, then v P NG rus. Observe also that a vertex can be a certiﬁcate for
many vertices and it can be a certiﬁcate for itself. Notice that in the case
of the classical domination, certiﬁcates are usually called privates because
a vertex is always a certiﬁcate for exactly one vertex, including itself. It is
straightforward to show the following.
Lemma 3. A set D Ď Red is a 1-minimal Red pσ, ρq-dominating set of a
colored graph G if and only if each vertex u P D has a certificate. Furthermore, D is a 1-maximal Red pσ, ρq-dominating set of G if and only if each
vertex u P RedzD has a certificate.

3

Enumerations for graphs of bounded LMIM-width

In this section we prove the following.
Theorem 4. Let pσ, ρq be a pair of finite or co-finite subsets of N and let
c be a positive integer. For a colored graph G given with a linear ordering
of V pGq of MIM-width at most c, one can count in time bounded by Opnc q,
and enumerate with linear delay, all 1-minimal (or 1-maximal) Red pσ, ρqdominating sets of G.
As a corollary of Theorems 1 and 4, and Proposition 2 we have the
following.
6

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 deﬁnitions and lemmas that are
important for the deﬁnition of the DAG whose maximal paths correspond
to the desired sets. In Section 3.2 we deﬁne 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.

3.1

Technical Definitions

First because σ and ρ can be inﬁnite, we need a ﬁnite way to check if a
vertex is pσ, ρq-dominated. Let dpNq “ 0. For every ﬁnite set µ Ď N,
let dpµq :“ 1 ` maxta | a P µu, and for every co-ﬁnite set µ Ď N, let
dpµq :“ 1 ` maxta | a P Nzµu. For ﬁnite or co-ﬁnite 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 NG pxq| up to dpσ, ρq for
each vertex x in Blue [6]. We need the following properties of certiﬁcates.
Lemma 7. Let D be a Red pσ, ρq-dominating set of colored graph G. If v
is a certificate for u P D, then v “ u or v is a certificate for all vertices
of NG pvq X D. If v is a certificate for u P D X Red, then v “ u or v is a
certificate for all vertices of NG pvq X D X Red.

7

Proof. Let v ‰ u be a certiﬁcate for u P D and let D 1 :“ Dztuu. If v P D 1
and |NG pvq X D 1 | R σ, then for any w P NG pvq X D, |NG pvq X pDztwuq| “
|NG pvqXD 1 | R σ. If v R D 1 and |NG pvqXD 1 | R ρ, then for any w P NG pvqXD,
|NG pvq X pDztwuq| “ |NG pvq X D 1 | R ρ. The second claim can be proved by
similar arguments.
We deﬁne σ ˚ :“ σzρ and ρ˚ :“ ρzσ. Let also σ ´ :“ ti P σ | i ´ 1 R σu,
:“ ti P ρ | i´ 1 R ρu, σ ` :“ ti P σ | i` 1 R σu and ρ` :“ ti P ρ | i` 1 R ρu.
By the deﬁnitions, we have the following property.
ρ´

Lemma 8. The sets σ ˚ , ρ˚ , σ ´ , ρ´ , σ ` , ρ` are finite or co-finite. Also,
dpσ ˚ , ρ˚ q ď dpσ, ρq, dpσ ´ , ρ´ q ď dpσ, ρq ` 1 and dpσ ` , ρ` q ď dpσ, ρq ` 1.
By the deﬁnition of certiﬁcates, 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
#
σ ´ if v P D
|NG pvq X D| P
ρ´ if v R D.
If u R D, then v is a certificate for u if and only if
#
σ ` if v P D
|NG pvq X D| P
ρ` if v R D.
A blue vertex v P D is a certificate for itself if and only if |NG pvq X D| P
σ ˚ . A red vertex v R D is a certificate for itself if and only if it is blue and
|NG pvq X D| P ρ˚ .
Let d P N and let A be a subset of the vertex set of a colored graph G.
Two red subsets X and Y of A are d-neighbor equivalent w.r.t. A, denoted
s X Blue we have
by X ”dA Y , if for all x P A
minpd, |X X NG pxq|q “ minpd, |Y X NG pxq|q.

It is not hard to check that ”dA is an equivalence relation and et us
denote by necp”dA q the number of equivalence classes of ”dA . 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
s X Blueq ď k. Then necp”d q ď nd¨k .
graph G such that mimG pA X Red, A
A

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.

Lemma 11 ([3]). Let G be a colored graph and let A be a subset of V pGq.
s X Blueq ď k if and only if for every blue subset
Then, mimG pA X Red, A
s there is C Ď S such that N pCq X pA X Redq “ N pSq X pA X Redq
S of A
and |C| ď k.
8

3.2

Constructing the DAG for 1-minimal sets

Throughout this section we let pσ, ρq be a ﬁxed pair of ﬁnite or co-ﬁnite
subsets of N and we let G be a ﬁxed n-vertex colored graph with n ě 2. Let
also x1 , . . . , xn be a ﬁxed linear ordering of the vertex set of G such that
the MIM-width of x1 , . . . , xn is bounded by a constant c. Furthermore, for
all i P t1, 2, . . . , nu, we let Ai “ tx1 , x2 , . . . xi u and Ai “ txi`1 , xi`2 , . . . xn u.
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 deﬁnitions and lemmas (restated in our setting) proved in [6]. For every i P t1, . . . , nu and every subset X of Ai X Red, we denote by repdAi pXq
the lexicographically smallest set R Ď Ai X Red such that |R| is minimised
and R ”dAi X. Notice that it can happen that R “ H.
Lemma 12 ([6]). For every i P t1, . . . , nu, one can compute a list LRi
containing all representatives w.r.t. ”dAi in time Opnecp”dAi q ¨ logpnecp”dAi
qq¨n2 q. One can also compute a data structure that given a set X Ď Ai XRed
in time Oplogpnecp”dAi qq ¨ |X| ¨ nq allows us to find a pointer to repdAi pXq in
LRi . Similar statements hold for the list LRsi containing all representatives
w.r.t. ”dA
Ď.
i

We will deﬁne a DAG, denoted by DAGpGq, the maximal paths of which
correspond exactly to the 1-minimal Red pσ, ρq-dominating sets of G.
sj X Blue) we denote by
For 1 ď j ď n and C Ď Aj X Blue (or C Ď A
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
sj XRedq
smallest) vertex in X such that N pXztxuqXpAsj XRedq “ N pXqXpA
(or N pXztxuq X pAj X Redq “ N pXq X pAj 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 Ď Aj XBlue
sj X Blue), then SG ℓ pC Y txℓ uq “ SG ℓ pSG j pCq Y txℓ uq for all ℓ ą j
(or C Ď A
(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 certiﬁcates in order to avoid
redundancies.
s
Let 1 ď j ă n and let pRj , Rj1 , Cj , Cj1 q P LRj ˆLRj̄ ˆ2Aj XBlue ˆ2Aj XBlue
sj`1 XBlue
A
XBlue ˆ 2A
1
1
.
and pRj`1 , Rj`1
, Cj`1 , Cj`1
q P LRj`1 ˆ LRj`1
Ě ˆ 2 j`1
1
1
There is an ε-arc-1 from pRj , Rj1 , Cj , Cj1 q to pRj`1 , Rj`1
, Cj`1 , Cj`1
q if
1
(1.1) Rj ”dAj`1 Rj`1 and Rj1 ”dAs Rj`1
, and
j

1
(1.2) if (xj`1 R Blue or (xj`1 P Blue and |N pxj`1 q X pRj Y Rj`1
q| P ρ and
1
´
|N pxj`1 q X pRj Y Rj`1 q| R ρ )) then (Cj`1 “ SG j`1 pCj q and Cj1 “
1
1
GG j pCj`1
q), otherwise we should have (|N pxj`1 q X pRj Y Rj`1
q| P ρ´ )
and

9

(1.2.a) if N pxj`1 qXpAsj`1 XRedq ‰ H, then Cj`1 “ SG j`1 pCj Ytxj`1 uq,
else Cj`1 “ SG j`1 pCj q, and

1
(1.2.b) if N pxj`1 q X pAj X Redq ‰ H, then Cj1 “ GG j pCj`1
Y txj`1 uq,
1
1
else Cj “ GG j pCj`1 q.
1
1
q if
There is an ε-arc-2 from pRj , Rj1 , Cj , Cj1 q to pRj`1 , Rj`1
, Cj`1 , Cj`1

1
(2.1) Rj`1 ”dAj`1 pRj Y txj`1 uq, Rj1 ”dAs pRj`1
Y txj`1 uq, xj`1 P Red,
j
1
(|N pxj`1 q X pRj Y Rj`1 q| P σ if xj`1 P Blue), and
1
(2.2) if (xj`1 R Blue or (xj`1 P Blue and |N pxj`1 q X pRj Y Rj`1
q| R σ ´ )),
1
then (Cj`1 “ SG j`1 pCj q and Cj1 “ GG j pCj`1
q), otherwise we should
1
´
have (|N pxj`1 q X pRj Y Rj`1 q| P σ ) and

(2.2.a) if N pxj`1 qXpAsj`1 XRedq ‰ H, then Cj`1 “ SG j`1 pCj Ytxj`1 uq,
else Cj`1 “ SG j`1 pCj q, and

1
(2.2.b) if N pxj`1 q X pAj X Redq ‰ H, then Cj1 “ GG j pCj`1
Y txj`1 uq,
1
1
else Cj “ GG j pCj`1 q, and

1
(2.3) either (N pxj`1 q X pCj Y Cj`1
q ‰ H) or (pxj`1 P Blue and |N pxj`1 q X
1
˚
pRj Y Rj`1 q| P σ ).
s

The nodes of DAGpGq. pR, R1 , C, C 1 , iq P LRi ˆLRī ˆ2Ai XBlue ˆ2Ai XBlue ˆ
rns is a node of DAGpGq whenever xi P Red, C “ SG i pCq and C 1 “ GG i pC 1 q.
We call i the index of pR, R1 , 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 pR0 , R01 , C0 , C01 , jq
to the node pRp , Rp1 , Cp , Cp1 , j ` pq with 1 ď j ă j ` p ď n if there exist
1
1
tuples pR1 , R11 , C1 , C11 q, . . . , pRp´1 , Rp´1
, Cp´1 , Cp´1
q such that (1) for each
sj`i XBlue
A
XBlue ˆ2A
1
1
j`i
and
1 ď i ď p´1, pRi , Ri , Ci , Ci q P LRj`i ˆLRj`i
Ě ˆ2
1
1
1
1
there is an ε-arc-1 from pRi´1 , Ri´1 , Ci´1 , Ci´1 q to pRi , Ri , Ci , Ci q, and (2)
1
1
q to pRp , Rp1 , Cp , Cp1 q.
, Cp´1 , Cp´1
there is an ε-arc-2 from pRp´1 , Rp´1
There is an arc from the source node to a node pR, R1 , C, C 1 , jq if (S “
sj X Redq ‰ H and |N pxq X ptxj u Y R1 q| P ρ´ u)
tx P pAj X Blueqztxj u | N pxq X pA

(S1) txj u ”dAj R and ptxj u Y R1 q pσ, ρq-dominates Aj X Blue,

(S2) if (xj P Blue and |N pxj qXR1 | P σ ´ ) then C “ SG j pS Ytxj uq, otherwise
C “ SG j pSq, and
(S3) either (N pxj q X pC 1 Y Cq ‰ H) or (xj P Blue and |N pxj q X R1 | P σ ˚ ).
There is an arc from a node pR, R1 , C, C 1 , jq to the terminal node if
10

sj`1 X Blue, and
(T1) |N pxq X R| P ρ for each x P A

sj X Blue | N pxq X pAj X Redq ‰ H and |N pxq X R| P
(T2) C 1 “ GG j ptx P A
´
ρ uq.
Lemma 13. DAGpGq is a DAG and can be constructed in time Opnc¨d q.

Proof. An arc is always oriented from a node pR, R1 , C, C 1 , jq to pR̂, R̂1 , Ĉ, Ĉ 1 , j`
pq with p ě 1. Therefore, we cannot create circuits, i.e., DAGpGq is a DAG.
For each index 1 ď i ď n and each node pR, R1 , 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 Opnc¨d q since necp”dAi q ď nd¨c by Lemma 10. Now,
constructing the arcs from the source node can be done in Opnc¨d q time since
it suﬃces to check for each node pR, R1 , C, C 1 , jq if conditions (S1)-(S3) are
satisﬁed, 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 Opnc¨d q time.
Now, to construct an arc from pR0 , R01 , C0 , C01 , jq to pRp , Rp1 , Cp , Cp1 , j `pq
we do as follows. For 0 ď i ď p ´ 1 we let Fi be a queue and we put
1 ,C
1
pR0 , R01 , C0 , C01 q in F0 . Now, for 1 ď i ď p ´ 1, pull pRi´1 , Ri´1
i´1 , Ci´1 q
1
1
1
from Fi´1 , and for each pR, R , C, C q with R P LRj`i , R P LRj`i
¯ , C Ď
1
1
s
Aj`i X Blue, C Ď Aj`i X Blue with |C|, |C | ď c such that there is an ε1 ,C
1
1
1
1
1
arc-1 from pRi´1 , Ri´1
i´1 , Ci´1 q to pR, R , C, C q, then put pR, R , C, C q
in Fi . Now, by the deﬁnition of an arc in DAGpGq there is an arc from
pR0 , R01 , C0 , C01 , jq to pRp , Rp1 , Cp , Cp1 , j ` pq if and only if there is one
1
1
q in Fp´1 such that there is an ε-arc-2 from
, Cp´1 , Cp´1
pRp´1 , Rp´1
1
1
pRp´1 , Rp´1 , Cp´1 , Cp´1 q to pRp , Rp1 , Cp , Cp1 , j ` pq. Now, the size of each Fi
is bounded by Opnc¨d q, and since the conditions of ε-arc-1 and ε-arc-2 can
be checked in Opnc¨d q time with the help of Lemma 12, we can check if there
is an arc between two nodes in time Opnc¨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, v1 , v2 , . . . , vp , tq is a path in DAGpGq, then the trace of P , denoted
by tracepP q, is deﬁned as txj1 , xj2 , . . . , xjp u where for all i P t1, 2, . . . , pu, ji
is the index of the node vi .
The following two lemmas are implied by the deﬁnition of the d-neighbor
equivalence and Lemma 8.
Lemma 14. Let pµ, µ1 q P tpσ, ρq, pσ ˚ , ρ˚ q, pσ ´ , ρ´ q, pσ ` , ρ` qu. Let also i P
d Y then
t1, . . . , nu, and X Ď Ai X Red and Y, Y 1 Ď Ai X Red. If Y 1 ”A
i
X Y Y pµ, µ1 q-dominates Ai X Blue if and only if X Y Y 1 pµ, µ1 q-dominates
Ai X Blue. Symmetrically, if X, X 1 Ď Ai X Red and Y Ď Ai X Red, and
si X Blue if and only if X 1 Y Y
X 1 ”dAi X, then X Y Y pµ, µ1 q-dominates A
si X Blue.
pµ, µ1 q-dominates A
11

Lemma 15. Let pµ, µ1 q P tpσ, ρq, pσ ˚ , ρ˚ q, pσ ´ , ρ´ q, pσ ` , ρ` qu, i P t1, . . . , nu
Ďi X Red. If
and let Z Ď Red. Let also X Ď Ai´1 X Red and Y Ď A
d
d
1
X ”Ai´1 pZ X Ai´1 q and Y ”A pZ X Ai q, then Z pµ, µ q-dominates txi u if
i
and only if pX Y Y Y pZ X txi uq pµ, µ1 q-dominates txi u.
The next lemma shows that two maximal paths in DAGpGq give rise to
two diﬀerent 1-minimal Red pσ, ρq-dominating sets.
Lemma 16. If there is a path P “ ps, v1 , . . . , vk , tq in DAGpGq, then
tracepP q is a 1-minimal Red pσ, ρq-dominating set of G. Moreover, tracepP q ‰
tracepP 1 q for any other path P 1 “ ps, v11 , . . . , vk1 , tq in DAGpGq.
Proof. Let P “ ps, v1 , . . . , vk , tq and tracepP q “ txj1 , . . . , xjk u. We will ﬁrst
prove by induction that for each 1 ď i ď k, the set Di “ txj1 , . . . , xji u
satisﬁes the following properties (with vi “ pRji , Rj1 i , Cji , Cj1 i , ji q)
(i) Rji P LRji , Rj1 i P LRj¯i ;
(ii) Di ”dAj Rji ,
i

(iii) Di Y Rj1 i pσ, ρq-dominates Aji X Blue;
(iv) Each u P Di is either adjacent to a vertex from Cj1 i , or has a certiﬁcate
in Aji X Blue.
(v) Cji “ SG ji pSi q, where Si is the set of vertices in Aji X Blue that are
sj X Red;
certiﬁcates and have a neighbor in A
i

By the deﬁnition 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 deﬁnition of the
arcs from the source node, we can easily check that the properties (ii)-(v)
are all veriﬁed 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 pRs , Rs1 , Cs , Cs1 q
1
1
q
, Cs´1 , Cs´1
for jℓ´1 `1 ď s ď jℓ ´1 such that there is an ε-arc-1 from pRs´1 , Rs´1
1
1
to pRs , Rs , Cs , Cs q for each jℓ´1 ` 1 ď s ď jℓ ´ 1, and there is an ε-arc-2
from pRjℓ ´1 , Rj1 ℓ ´1 , Cjℓ ´1 , Cj1 ℓ ´1 q to pRjℓ , Rj1 ℓ , Cjℓ , Cj1 ℓ q. By the conditions
(1.1) and (2.1) we can conclude that Djℓ ”dAj Rjℓ because Djℓ´1 ”dAs Rs for
ℓ

all jℓ´1 ` 1 ď s ď jℓ ´ 1 by the condition (1.1) and Rjℓ ”dAj pRjℓ ´1 Y txjℓ uq
ℓ
by the condition (2.1).
1
Rs´1
for each jℓ´1 ` 1 ď s ď jℓ ´ 1 by (1.1) and
Because Rs1 ”dAs
s´1

Rj1 ℓ ´1 ”dAs

jℓ ´1

Rj1 ℓ Y txjℓ 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 xs P Blue it is pσ, ρq-dominated by Djℓ Y Rj1 ℓ , thus proving
(iii).
12

In order to check (iv) and (v), we let Ds “ Djℓ´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 deﬁnition of the d-neighbor equivalence
and the fact that Ds X Rs1 “ H.
ss X Blue, we have pDs Y R1 q pσ ´ , ρ´ q-dominates tvu if
1. For each v P A
s
and only if pRs Y Rs1 q pσ ´ , ρ´ q-dominates tvu; and |N pvq X Ds | ‰ 0 if
and only if |N pvq X Rs | ‰ 0.
2. For each v P As´1 X Blue, we have pDs Y Rs1 q pσ ´ , ρ´ q-dominates tvu
1
q pσ ´ , ρ´ q-dominates tvu;
if and only if pDs´1 Y Rs´1
3. pDs Y Rs1 q pσ ´ , ρ´ q-dominates txs u if and only if pRs´1 Y Rs1 q pσ ´ , ρ´ qdominates txs u.
4. Each u P Ds´1 either has a certiﬁcate in As w.r.t. Ds or is adjacent
to a vertex from Cs1 . Indeed, either it has by induction a certiﬁcate
v from As´1 w.r.t. Ds´1 and by (2) and Lemma 9 the vertex v is
still a certiﬁcate for u w.r.t. Ds , or u is adjacent to some vertex in
1
Cs´1
and then by induction and the conditions (1.2) and (2.2) either
it is adjacent to some vertex in Cs1 or it is adjacent to xs which is
pσ ´ , ρ´ q-dominated by Ds Y Rs1 following fact 3.
From the facts 1. and 2. we can conclude that pDs Y Rs1 q pσ ´ , ρ´ qdominates Cs for all jℓ´1 `1 ď s ď jℓ . Hence, pDjℓ YRj1 ℓ q pσ ´ , ρ´ q-dominates
Cjℓ . Moreover, from the fact 4. we know that each u P Djℓ´1 is either
adjacent to a vertex in Cj1 ℓ or has a certiﬁcate w.r.t. Djℓ in Ajℓ X Blue. In
order to prove that (iv) is satisﬁed it remains then to check that xjℓ has a
certiﬁcate in Ajℓ 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 suﬃcient to notice that whenever
xs is pσ ´ , ρ´ q-dominated by pDs Y Rs1 q for each jℓ´1 ` 1 ď s ď jℓ , by the
condition (1.2.a) and (2.2.a) Cs “ SG s pCs´1 Y xs q, and this guarantees by
inductive hypothesis, the fact 2. and Lemma 9 that Cs is exactly SG s pSs q
where Ss is the set of vertices in As X Blue that are certiﬁcates and have a
ss .
neighbor in A
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 Cj1 i “ GG ji pSi1 q where Si1 is the set of
sj X Blue that are pσ ´ , ρ´ q-dominated by Dj Y R1 and have a
vertices in A
i
i
ji
neighbor in Aji XRed. By the condition (T2) in the deﬁnition of an arc to the
terminal node this is satisﬁed by Cj1 k . So, if we assume that Cj1 i “ GG ji pSi1 q
for all ℓ ă i ď k, then as for the condition (v) the inductive hypothesis, the
fact 2. and Lemma 9 guarantees that Cj1 ℓ is exactly GG jℓ pSℓ1 q.
13

So now for each i the sets Cji and Cj1 i are uniquely determined by
tracepP q, which means that whenever tracepP q “ tracepP 1 q because ”dA 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.
Lemma 17. If G has a 1-minimal Red pσ, ρq-dominating set D, then there
is a path P “ ps, v1 , v2 , . . . , vk , tq in DAGpGq such that D “ tracepP q.
Proof. Let D “ txj1 , . . . , xjk u such that j1 ă j2 ă ¨ ¨ ¨ ă jk . For each
i P t1, . . . , ku, we let Di “ txj1 , . . . , xji u. Let also Rji P LRji be such that
sj q. For each i
Rji ”dAj Di , and let Rj1 i P LRj¯i be such that Rj1 i ”dAs pD X A
i
ji

i

we let Cji “ SG ji pSi q where Si is the set of vertices in Aji X Blue that are
sj XRed and similarly let C 1 “ GG j pS 1 q
certiﬁcates and have a neighbor in A
i
i
ji
i
sj X Blue that are certiﬁcates and have
where Si1 is the set of vertices in A
i
a neighbor in Aji X Red. Hence, vi “ pRji , Rj1 i , Cji , Cj1 i , ji q is a node of
DAGpGq for each 1 ď i ď k.
We ﬁrst observe that there is an arc from the source node s to v1 . Indeed,
by the deﬁnition of Rji , Rj1 i , we have that txj1 u ”dAj Rj1 and txj1 u Y Rj1 1
1
pσ, ρq-dominates Aj1 , and by the choices of Cji and Cj1 i the condition (S2)
is satisﬁed and since xj1 has a certiﬁcate w.r.t. D, the condition (S3) is
satisﬁed. For similar reasons one can prove that there is an arc from vk to
the terminal node t.
We now claim that there is an arc from vi to vi`1 for 1 ď i ă k. For each
ji ă s ă ji`1 , we let pRs , Rs1 , Cs , Cs1 q be such that Rs ”dAs Rs´1 , Rs1 ”dAs
s´1

1
, and Rji`1 ”dAj
Rs´1

i`1

Rji`1 ´1 Y txji`1 u and Rj1 i`1 ´1 ”dAs

ji`1 ´1

Rj1 i`1 Y

txji`1 u. It is straightforward to prove by induction on ji`1 ´ ji that there
1
1
q to pRs , Rs1 , Cs , Cs1 q for each
, Cs´1 , Cs´1
exists an ε-arc-1 from pRs´1 , Rs´1
ji ă s ă ji`1 and there is an ε-arc-2 from pRji`1 ´1 , Rj1 i`1 ´1 , Cji`1 ´1 , Cj1 i`1 ´1 q
to pRji`1 , Rj1 i`1 , Cji`1 , Cj1 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 suﬃces 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 “ v1 , v2 , . . . , vm “ t. Since
DAGpGq is a DAG, any arc is of the form pvi , vj q with i ă j. The counting

14

will follow this topological ordering. We initially set N ppvq “ ´1 for all
nodes v ‰ t and we set N ppvm q “ 1. For each j ă m we let
ÿ
N ppvℓ q.
N ppvj q “
pvj ,vℓ qPEpDAGpGqq
N ppvℓ q‰´1

Fact 19. One can compute the values of N ppvj q for all j P t1, 2, . . . , mu in
time Opnc¨d q.
Proof. By induction on j. By deﬁnition 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 ppvj q we ﬁrst set a counter nb to 0, and add
N ppvℓ q to nb whenever pvj , vℓ q P EpDAGpGqq and N ppvℓ q ‰ ´1. We ﬁnally
set N ppvj q to nb. The correctness of the computation of N ppvj q follows
from the deﬁnition. Since the degree of a node is bounded by Opnc¨d q, we
can update nb in time Opnc¨d q. Now since the number of nodes and of arcs
is bounded by Opnc¨d q, we obtain the claimed running time.
For 1 ď j ď m, we let Sj “ tP | P is a path starting at vj and ending at
tu. One can prove easily by induction the following.
Ţ
Lemma 20. Sj “
tvj ` P | P P Sℓ u for each 1 ď j ď m.
pvj ,vℓ qPEpDAGpGqq
N ppvℓ q‰´1

The following follows directly from the deﬁnition of N ppvj q and Lemma
20.
Lemma 21. |Sj | “ N ppvj q for each 1 ď j ď m.
Theorem 22. One can count the number of 1-minimal Red pσ, ρq-dominating
sets of a given graph G in time Opnc¨d q.
Proof. We ﬁrst construct the DAG DAGpGq and by Lemma 13 this can be
done in time Opnc¨d q. By Proposition 18 the mapping which associates with
every path P P S1 its trace tracepP q is a one-to-one correspondence between
S1 and all the 1-minimal Red pσ, ρq-dominating set in G. So, it is enough
to determine the size of S1 . By Lemma 21, |S1 | “ N ppsq and since by Fact
19 we can compute in time Opnc¨d q all the values N ppvj q for all 1 ď j ď m,
we conclude that one can compute in time Opnc¨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
xj of G. The algorithm is depicted in Figures 1 and 2. The algorithm consists
in enumerating the paths in S1 in a Depth-First Search manner.

15

Algorithm EnumMinDompDAGpGqq
1. Remove all nodes v such that N ppvq “ ´1
2. for each ps, vi q P EpDAGpGqq
3. EnumPathpDAGpGq, tvertpvi qu, vi q
4. end for

Figure 1: The enumeration of 1-minimal Red pσ, ρq-dominating sets
Algorithm EnumPathpDAGpGq, S Ď V pGq, vi q
1. if vi “ t, then output S and stop
2. for each pvi , vj q P EpDAGpGqq
3. EnumPathpDAGpGq, S Y tvertpvj qu, vj q
4. end for

Figure 2: The enumeration of Si
Theorem 23. We can enumerate all the 1-minimal Red pσ, ρq-dominating
sets of a given graph G with linear delay and with polynomial space.
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, vi q uses Opnc¨d q space and enumerates the
set tS Y P | P P Si u, the delay between two consecutive outputs P1 and
P2 bounded by Op|P2 zP1 |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
Opnc¨d q space.

3.3

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 diﬀerence with the
case of 1-minimal pσ, ρq-dominating set is that now we have to ensure that
xj has a certiﬁcate when xj is not included in a partial solution.
16

The nodes of DAGM pGq. pR, R1 , C, C 1 , iq P LRi ˆ LRī ˆ 2Ai XBlue ˆ
s
2Ai XBlue ˆ rns is a node of DAGM pGq whenever xi P Red, C “ SG i pCq
and C 1 “ GG i pC 1 q. We call i the index of pR, R1 , 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 pR0 , R01 , C0 , C01 , jq to pRP , Rp1 , Cp , Cp1 , j`
1
1
q
, Cp´1 , Cp´1
pq with j ă j`p ď n if there exist pR1 , R11 , C1 , C11 q, . . . , pRp´1 , Rp´1
sj`i XBlue
1
1
A
XBlue
A
j`i
such that pRi , Ri , Ci , Ci q P LRj`i ˆ LRj`i
ˆ2
for all
¯ ˆ2
1 ď i ď p ´ 1, and
(A1) for each 0 ď i ď p ´ 2,
(1.1) Ri ”dAj`i`1 Ri`1 and Ri1 ”dAs

j`i“1

1 , and
Ri`1

(1.2) if (xj`i`1 R Blue or (xj`i`1 P Blue and |N pxj`i`1 q X pRi Y
1 q| P ρ and |N px
1
`
Ri`1
j`i`1 q X pRi Y Ri`1 q| R ρ )) then (Ci`1 “
1
1
SG j`i`1 pCi q and Ci “ GG j`i pCi`1 q), otherwise we should have
1 q| P ρ` ) and
(|N pxj`i`1 q X pRi Y Ri`1
sj`i`1 XRedq ‰ H, then Ci`1 “ SG j`i`1 pCi Y
(1.2.a) if N pxj`i`1 qXpA
txj`i`1 uq, else Ci`1 “ SG j`i`1 pCi q, and
1
(1.2.b) if N pxj`i`1 q X pAj`i X Redq ‰ H, then Ci1 “ GG j`i pCi`1
Y
1
1
txj`i`1 uq, else Ci “ GG j`i pCj`i`1 q.

1 q ‰ H) or
(1.3) if xj`i`1 P Red, then either (N pxj`i`1 q X pCi Y Ci`1
1
˚
(pxj`i`1 P Blue and |N pxj`i`1 q X pRi Y Ri`1 q| P ρ ).
d
1
pRp1 Y txj`p uq, xj`p P Red,
”A
(A2) Rp ”dAj`p pRp´1 Y txj`p uq, Rp´1
j`p´1
and

(2.1) if xj`p P Blue, then |N pxj`p q X pRp´1 Y Rp1 q| P σ,
(2.2) if (xj`p R Blue or (xj`p P Blue and |N pxj`p q X pRp´1 Y Rp1 q| R
1
“ GG p´1 pCp1 q), otherwise
σ ` )), then (Cp “ SG p pCp´1 q and Cp´1
we should have (|N pxj`p q X pRp´1 Y Rp1 q| P σ ` ) and
sp XRedq ‰ H, then Cp “ SG p pCp´1 Ytxj`p uq,
(2.2.a) if N pxj`p qXpA
else Cp “ SG p pCp´1 q, and
1
“ GG p´1 pCp1 Y
(2.2.b) if N pxj`p q X pAp´1 X Redq ‰ H, then Cp´1
1
“ GG p´1 pCp1 q.
txj`p uq, else Cp´1
We now deﬁne arcs from the source node. There is an arc from the source
node to a node pR, R1 , C, C 1 , jq if (S “ tx P pAj X Blueqztxj u | N pxq X pAsj X
Redq ‰ H and |N pxq X ptxj u Y R1 q| P ρ` u)

(S1) txj u ”dAj R and ptxj u Y R1 q pσ, ρq-dominates Aj X Blue,
17

(S2) if (xj P Blue and |N pxj qXR1 | P σ ` ) then C “ SG j pS Ytxj uq, otherwise
C “ SG j pSq, and
(S3) for each red vertex x P Aj ztxj u, either (N pxq X pC 1 Y Cq ‰ H) or
(x P Blue and |N pxq X pR1 Y Rq| P ρ˚ ).
We ﬁnally deﬁne the arcs to the terminal node. There is an arc from a
node pR, R1 , C, C 1 , jq to the terminal node if
sj`1 X Blue, and
(T1) |N pxq X pR Y R1 q| P ρ for each x P A

sj X Blue | N pxq X pAj X Redq ‰ H and |N pxq X R| P
(T2) C 1 “ GG j ptx P A
ρ` uq,
sj , then N pxq X pC Y C 1 q ‰ H or (|N pxq X pR Y
(T3) for each red vertex in A
R1 q| P ρ˚ if x P Blue).
DAGM pGq is clearly a DAG, and as for DAGpGq one can construct it
in time Opnc¨d q. Similarly, one can observe that if P :“ ps, v1 , . . . , vk , tq is
a maximal path from the source node to the terminal node, then if we let
Di :“ txj1 , . . . , xji u with vi :“ pRji , Rj1 i , Cji , Cj1 i , ji qq, then
(i) Rji P LRji , Rj1 i P LRj¯i ;
(ii) Di ”dAj Rji ,
i

(iii) Di Y Rj1 i pσ, ρq-dominates Aji X Blue;
(iv) Each u P Aji zDi is either adjacent to a vertex from Cj1 i , or has a
certiﬁcate in Aji X Blue.
(v) Cji “ SG ji pSi q, where Si is the set of vertices in Aji X Blue that are
sj X Red;
certiﬁcates and have a neighbor in A
i

sj X Blue that are
(vi) Cj1 i “ GG ji pSi1 q where Si1 is the set of vertices in A
i
certiﬁcates and have a neighbor in Aji 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 Opnc¨d q the number of 1-maximal Red pσ, ρq-dominating sets
in G.

18

4

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].

4.1

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 Ñ Q2 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 “ xf pxq ´ txf 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 | xf “ xu is a non-empty proper subset of
V pGq, then mimG pA, Aq ď h.
s Denote by MA
Proof. Let M be a maximum induced matching in GrA, As.
the set of end-vertices of the edges of M in A and let MB be the set of
s As all the vertices of MA have the same
end-vertices of the matching in A.
x-coordinate, and each vertex of MB is adjacent to some vertex in MA , a
vertex u P MA is adjacent to a vertex v P MB only if |yf puq ´ yf pvq| ă 1.
Denote by a1 , . . . , ak and b1 , . . . , bk the vertices of MA and MB respectively
and assume that they are ordered by the increase of their y-coordinates.
We claim that ai bi P M for i P t1, . . . , ku. To obtain a contradiction,
suppose that there is ai that is not adjacent to bi and choose the minimum
index i for which it holds. Then ai bj P M and bi as P M for some j, s ą i.
If bi is adjacent to as but not ai , we must have |yf pbi q ´ yf pai q| ě 1 and
|yf pbi q ´ yf pas q| ă 1. Since yf pas q ě yf pai q, yf pbi q ě yf pai q ` 1. But
as yf pbj q ě yf pbi q ě yf pai q ` 1, bj and ai cannot be adjacent after all; a
contradiction.
Now we show that yf pai q ě yf pbi´1 q ` 1 and yf pbi q ě yf pai´1 q ` 1
for i P t2, . . . , ku. Because ai´1 bi´1 P M , |yf pai´1 q ´ yf pbi´1 q| ă 1. As
ai´1 bi , ai bi´1 R EpGq, |yf pai´1 q ´ yf pbi q| ě 1 and |yf pai q ´ yf pbi´1 q| ě 1.
We have that yf pai q ě yf pbi´1 q ` 1 and yf pbi q ě yf pai´1 q ` 1, because
yf pai q ě yf pai´1 q and yf pbi q ě yf pbi´1 q.
Next, we claim that yf pai q, yf pbi q ě i. Clearly, yf pa1 q, yf pb1 q ě 1. Because yf pai q ě yf pbi´1 q ` 1 and yf pbi q ě yf pai´1 q ` 1 for i P t2, . . . , ku, we
19

have that claim holds for all i P t1, . . . , ku by induction.
s “ k ď h.
Because k ď yf pak q ď h, we conclude that mimG pA, Aq

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 v1 , . . . , vn be the vertices of G ordered by increasing frac-value,
i.e., fracpvi q ď fracpvj q if i ď j. We show that this is an ordering of MIMwidth at most 2hw.
s ě
For contradiction, assume that for some i P t1, . . . , n´1u, mimG pA, Aq
s has an induced
2hw ` 1 where A “ tv1 , . . . , vi u, i.e., the graph GrA, As
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 txf pvqu “ p.
Denote this subset of A X V pM q by CA , and denote by CB the vertices of
V pM qzA adjacent to CA . Let t “ maxtfracpvq | v P Au, and observe that
tv | fracpvq ă tu Ă A and tv | fracpvq ą tu X A “ H. We now partition
ăt “ tv P C | fracpvq ă tu and C “t “ tv P C |
CA into two parts CA
A
A
A
fracpvq “ tu and argue that neither of these parts can be of size more than
h, contradicting that |CA | ě 2h ` 1.
“t | ď h. For each v P C “t , tx pvqu “ p and
We ﬁrst show that |CA
f
A
“t . By Lemma 25, the size of
fracpvq “ t. Hence, xf pvq “ p ` t for all v P CA
“t , C s is at most h and this implies
the maximum induced matching in GrCA
B
“t
that |CA | ď h.
ăt | ď h, we will show that for the sake of the induced
To show that also |CA
ăt might as well have
matching, all the x-coordinates of the vertices v of CA
fracpvq “ 0, and therefore we can apply Lemma 25.
ăt . Then we construct a new vertex v 1 represented by the
Let v P CA
point ptxf pvqu, yf pvqq. We will now show that v 1 is adjacent to a vertex
u P CB 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 |xf pvq ´ xf puq| ă 1 if and only if
|txf pvqu ´ xf puq| ă 1.
Suppose that v is adjacent to u but v 1 is not. Because xf pvq ě txf pvqu, we
have that txf pvqu ` 1 ě xf puq ą xf pvq ` 1. However, that means fracpuq ď
fracpvq ă t, which implies that u P A contradicting u P CB . Similarly,
suppose v 1 is adjacent to u but v is not. Now txf pvqu´1 ă xf puq ď xf pvq´1,
which again implies that fracpuq ď fracpvq ă t, contradicting that u is in
CB .
ăt u, where each v 1 is represented by the point
Consider S “ tv 1 | v P CA
ptxf pvqu, yf pvqq “ pp, yf pvqq. Because each v 1 P S is adjacent to u P CB if
ăt | “ |S| ď h.
and only if v is adjacent to u, by Lemma 25, |CA
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
20

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 Ñ Q2 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, lmimwpGrNGr russq “ Opr 2 q. Moreover, if a realization f : V pGq Ñ Q2 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 mintxf pvq | v P NGr rusu “ mintyf pvq | v P NGr rusu “ 1. Otherwise, we
can shift the points representing vertices. For any v P NGr rus, |xf puq ´
xf pvq| ď r and |yf puq ´ yf pvq| ď r. We obtain that f pvq P r1, 2r ` 1s ˆ
r1, 2r`1s. By Lemma 26, lmimwpGrNGr russq “ Opr 2 q and the corresponding
ordering of the vertices can be constructed in polynomial time.

4.2

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 ﬂipping 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
ﬂipping operation is applied to every appropriate minimal dominating set
found, to ﬁnd new minimal dominating sets inducing subgraphs with more
edges.
Let G be a graph. Let also D Ď V pGq. For u P D, CD rus “ tv P V pGq |
v P NG ruszNG rDztvusu and CD puq “ tv P V pGq | v P NG puqzNG rDztvusu “
CD rusztuu. Observe that if D is a minimal dominating set, then CD puq is
the set of certiﬁcates for a vertex u P D.
Let us describe the variant of the ﬂipping operation from [12], that we
use. Let G be the input graph; we ﬁx an (arbitrary) order of its vertices:
v1 , . . . , vn . 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 v1 , . . . , vn ) if we initially let D “ D 1 , and then
recursively apply the following rule: If D is not minimal, then find a vertex
vi with the smallest index i such that Dztvi u is a dominating set in G, and

21

set D “ Dztvi u. Clearly, when we apply this rule, we never remove vertices of D 1 that have certiﬁcates. 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, CD rus “ CD puq ‰ H. Let X be an non-empty inclusion-maximal
independent set such that X Ď CD puq. Consider the set D 1 “ pDztuuq Y X.
Notice that D 1 is a dominating set in G, since all vertices of CD 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
certiﬁcates 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 deﬁnition 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 certiﬁcates 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 D ˚
from D; i.e., it replaces a non-empty independent set X in GrD ˚ s such that
X Ď GrD ˚ sXNG 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 deﬁned 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 Ď NG puq
such that D ˚ is a parent with respect to ﬂipping 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 ﬂipping of any u P D X NG rDztuus and
a maximal independent set X Ď CD puq, as Z is lexicographically ﬁrst sets
selected by a greedy algorithm. Similarly, we say that D is a child of D ˚
(with respect to ﬂipping u and X) if D ˚ is the parent of D (with respect to
ﬂipping 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 Ď
NG 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 ˚ XNG puq, generates with polynomial delay a family of minimal dominating
sets D with the property that D contains all minimal dominating sets D
22

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 GrNG3 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 NG 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 Ď NG pXqzNG rus. Therefore,
Blue Ď NG2 rus. Let Red “ NG pBlueqzNG rXs. Clearly, Red Ď NG3 rus. We
construct the colored graph H “ GrRed Y Blues. Let A1 be an algorithm
that enumerates minimal Red dominating sets in H. Assume that if Blue “
H, then A1 returns H as the unique Red dominating set. We construct A
as follows.
Step 1. If A1 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 A1 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 certiﬁcate in B.
Therefore, the greedy removal never deletes vertices of R. Since all sets R
generated by A1 are pairwise distinct, the claim follows.
Let D be a child of D ˚ with respect to ﬂipping 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 deﬁnition of X and Z. Hence,
Z X Blue “ H. Because D is minimal, each vertex of Z has a certiﬁcate. As
only the vertices of Blue are not dominated by pD ˚ Y tuuqzX, each vertex of
Z has its certiﬁcate in Blue. It remains to observe that Z dominates Blue,
to see that Z is a minimal Red dominating set of H. Because A1 generates
all minimal Red dominating sets, we have that D P D.
23

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 Ď NG puq has at most 4 vertices. Hence, all
independent sets X Ď NG 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.

References
[1] E.D. Demaine, F.V. Fomin, M. Hajiaghayi, D.M. Thilikos. Bidimensional parameters and local treewidth. SIAM J. Discrete Math. 18(3),
501-âĂŞ511 (2004).
[2] E.D. Demaine, M. Hajiaghayi, D.M. Thilikos. The bidimensional theory
of bounded-genus graphs. SIAM J. Discrete Math. 20(2), 357âĂŞ-371
(2006).
[3] R. Belmonte, M. Vatshelle. Graph classes with structured neighborhoods and algorithmic applications. Theor. Comput. Sci. 511, 54–65
(2013).
[4] A. Brandstädt, V.B. Le, J.P. Spinrad. Graph classes: a survey.
SIAM Monographs on Discrete Mathematics and Applications, SIAM,
Philadelphia, PA (1999).
[5] H. Breu. Algorithmic aspects of constrained unit disk graphs. PhD thesis, The University of British Columbia (1996).
[6] B.M. Bui-Xuan, J.A. Telle, M. Vatshelle. Fast dynamic programming
for locally checkable vertex subset and vertex partitioning problems.
Theor. Comput. Sci. 511, 66–76 (2013).
[7] L.S. Chandran, M.C. Francis, N. Sivadasan. On the cubicity of interval
graphs. Graphs and Combinatorics 25(2), 169–179 (2009).
[8] B. Courcelle. Linear delay enumeration and monadic second-order logic.
Discrete Applied Mathematics 157, 2675–2700 (2009).
[9] T. Eiter, G. Gottlob. Identifying the minimal transversals of a hypergraph and related problems. SIAM J. Comput. 24, 1278–1304 (1995).

24

[10] T. Eiter, G. Gottlob. Hypergraph transversal computation and related
problems in Logic and AI. Proceedings of JELIA 2002, LNCS 2424,
pp. 549–564 (2002).
[11] T. Eiter, G. Gottlob, K. Makino. New results on monotone dualization
and generating hypergraph transversals. SIAM J. Comput. 32, 514–537
(2003).
[12] P. A. Golovach, P. Heggernes, D. Kratsch, Y. Villanger. An incremental
polynomial time algorithm to enumerate all minimal edge dominating
sets. Algorithmica 72, 836-859 (2015).
[13] P. A. Golovach, P. Heggernes, M. Kante, D. Kratsch, Y. Villanger. Enumerating minimal dominating sets in chordal bipartite graphs. Discrete
Applied Mathematics, to appear. DOI 10.1016/j.dam.2014.12.010.
[14] D.S. Johnson, C.H. Papadimitriou, M. Yannakakis. On generating all
maximal independent sets. Inf. Process. Lett. 27(3), 119–123 (1988).
[15] M. M. Kanté, V. Limouzy, A. Mary, L. Nourine. On the enumeration of
minimal dominating sets and related notions. SIAM J. Discrete Math.
28, 1916–1929 (2014).
[16] M. M. Kanté, V. Limouzy, A. Mary, L. Nourine. On the Neighbourhood
Helly of some Graph Classes and Applications to the Enumeration of
Minimal Dominating Sets. Proceedings of ISAAC 2012, LNCS 7676,
pp. 289–298 (2012).
[17] M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine, T. Uno,. On the
Enumeration and Counting of Minimal Dominating sets in Interval and
Permutation Graphs. Proceedings of ISAAC 2013, LNCS 8283, pp. 339349 (2013).
[18] M. M. Kanté, V. Limouzy, A. Mary, L. Nourine, T. Uno. A Polynomial
Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal
Graphs. Proceedings of WG 2015, to appear. arXiv:1407.2036 (2014).
[19] M. M. Kanté, V. Limouzy, A. Mary, L. Nourine, T. Uno. Polynomial
Delay Algorithm for Listing Minimal Edge Dominating sets in Graphs.
Proceedings of WADS 2015, LNCS 9214, pp. 446-357 (2015).
[20] L. Khachiyan, E. Boros, K. Borys, K. M. Elbassioni, V. Gurvich. Generating all vertices of a polyhedron is hard. Discrete & Computational
Geometry 39, 174–190 (2008).
[21] L. Khachiyan, E. Boros, K. M. Elbassioni, V. Gurvich. On enumerating
minimal dicuts and strongly connected subgraphs. Algorithmica 50, 159–
172 (2008).
25

[22] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan. Generating all maximal independent sets: NP-hardness and polynomial-time algorithms.
SIAM J. Comput. 9, 558–565 (1980).
[23] I. Rauf. Polynomially Solvable Cases of Hypergraph Transversal and
Related Problems. PhD thesis, Saarland University (2011).
[24] R. E. Tarjan. Enumeration of the elementary circuits of a directed graph.
SIAM J. Comput. 2, 211–216 (1973).
[25] J.A. Telle, A. Proskurowski. Algorithms for vertex partitioning problems
on partial k-trees. SIAM J. Discrete Math. 10(4), 529–550 (1997).
[26] M. Vatshelle. New width parameters of graphs. PhD thesis, University
of Bergen (2012).

26

