On fixed-parameter tractability of the mixed domination
problem for graphs with bounded tree-width
M. Rajaati1 , M. R. Hooshmandasl2 , M. J. Dinneen3 , A. Shakiba4

arXiv:1612.08234v1 [cs.DM] 25 Dec 2016

1,2

Department of Computer Science, Yazd University, Yazd, Iran.
The Laboratory of Quantum Information Processing, Yazd University, Yazd, Iran.
3
Department of Computer Science, The University of Auckland, New Zealand.
4
Department of Computer Science, Vali-e-Asr University of Rafsanjan, Rafsanjan, Iran.
e-mail:1 m.rajaati@stu.yazd.ac.ir, 2 hooshmandasl@yazd.ac.ir, 3 m.dinneen@auckland.ac.nz, 4 ali.shakiba@vru.ac.ir.
1,2,4

Abstract
A mixed dominating set for a graph G = (V, E) is a set S ⊆ V ∪ E such that every element
x ∈ (V ∪ E)\S is either adjacent or incident to an element of S. The mixed domination number of a
graph G, denoted by γm (G), is the minimum cardinality of mixed dominating sets of G and any mixed
dominating set with cardinality of γm (G) is called a minimum mixed dominating set. The mixed
domination problem is to find a minimum mixed dominating set for graph G and is known to be an NPcomplete problem. In this paper, we present a novel approach to solve the mixed domination problem.
Our new technique of assigning power to edges and vertices, and charging vertices for edges combined
2
with with dynamic programming leads to a fixed-parameter algorithm of time O(3tw × tw2 × |V |),
which proves our next result, which is the mixed domination problem is fixed-parameter tractable
with respect to tree-width.
Keywords: Mixed Domination; Tree decomposition; Tree-width; Fixed-parameter tractable.

1

Introduction

The mixed domination problem, traditionally called total cover problem, is first introduced in 1977 by
Alavi et. al. [4]. This problem is shown to be NP-complete for general graphs in [18]. So, several approximation algorithms are proposed for solving this problem such as a 2-factor approximation algorithm
by Hatami [12]. Like most interesting hard problems, mixed domination for several special classes of
graphs such as split graphs remains NP-complete due to the high tree-width of their graph structure [15].
However, it is tractable for some graph classes such as cacti and trees [15]. Moreover, a parallel concept is used by Adhar et al. to solve the mixed domination problem in [1]. Their parallel NC algorithm
requires O(n) processors in CRCW PRAM model to solve the mixed domination problem in O(log n)
time, where n is the number of graph vertices. The mixed domination problem has many practical applications such as placing phase measurement units, or PMUs, in an electric power system [18]. The mixed
Roman domination problem and signed mixed Roman domination problem are generalizations of the
mixed domination problem that Abdollahzadeh et al. presented bounds for the mixed Roman domination
number and signed mixed Roman domination number [2, 3].
There exist different approaches to solve an NP-complete problem such as approximation, randomization, heuristics and parameterization. The parameterization method is a well known technique that
1

fixes certain parameters of the input to get a polynomial time algorithm with respect to the size of the
input and contain exponential terms which only depend on those fixed parameters. A famous example of
such parameters is the tree-width which is introduced by Robertson and Seymour in 1984 [16]. The treewidth parameter has proven to be a good measure of the intrinsic difficulty for various NP-hard problems
on graphs. The tree decomposition of a graph shows the similarity of the graph to a tree and is measured
by the tree-width. Most of the algorithms on the trees work efficiently, so tree decomposition of a graph
can be used to speed up solving some problems on graphs with a small tree-width.
Despite the fact that some problems in graph theory cannot be solved in polynomial time even with
constant tree-width, a large number of such problems are shown to be solvable in linear or polynomial
time. In general, there are two methods to handle the intractability of a problem with constant tree-width.
The first one uses monadic second-order logic. Since Courcelle proposed a surprising theorem which
states that if a graph property can be modeled in monadic second-order logic, then there exists a finite
automata or a Fly automata to check this property in linear time on graphs with a bounded tree-width [10].
The second technique is to use reductions. Bodlaender proposed interesting results which extends graph
reductions to graphs with bounded tree-width [7]. Using this technique, one can study variants of many
decision problems and by using a variant of these reduction algorithms, can solve optimization problems
in the linear time with respect to constant tree-width [7].
Recent investigations show that algorithms which solve intractable problems act more efficiently
when their input graphs are restricted to bounded tree-width ones. Much of these studies uses dynamic
programming techniques to solve the problem. For example, Chimani proposed an algorithm to solve
the Steiner tree problem on graphs using a well-known dynamic programming paradigm over the tree
decomposition of graph and utilizes a special numbering and coloring scheme to save various states. The
size of the table it computes is bounded by O(Bk+2 × tw) where Bk is the Bell number which is the
number of partitions of a k-element set [8].
In this paper, we propose a novel technique of charging power to vertices and edges, and use it
in accordance with dynamic programming to compute the mixed domination number for graphs with
2
bounded tree-width with O(3tw × tw2 × |V |) time complexity which is a polynomial algorithm with
respect to a fixed tree-width. The fundamental idea we use to solve the problem is to assign a power
value to vertices. This way, we have shown for the first time that the mixed domination problem is
fixed-parameter tractable with respect to tree-width.
The rest of this paper is organized as follows. In Section 2, we give necessary notations and definitions. In Section 3, we define a concept which is a key part of our proposed algorithm. Our algorithm to
solve the mixed domination problem is presented in Section 4. Also, we extend our algorithm in order
to find the elements of a minimum mixed domination set in this section. In Section 5, we formally prove
the correctness of the proposed algorithm. Finally, we give a conclusion and ideas for future works in
Section 6.

2

Preliminaries

In this section, we overview the graph theory that are used through out the paper. If required, an interested
reader can consult [17] and [13] for more deep introductions to graph theory.
Let G = (V, E) be a simple undirected graph. For each vertex v ∈ V , N (v) denotes the open
neighborhood of v defined as N (v) = {u | uv ∈ E} and its closed neighborhood is defined as N (v)∪{v}
which is denoted by N [v]. The nodes of a graph G, except for trees, are called vertices throughout this
paper.
Definition 2.1. Let G = (V, E) be a graph. A tree decomposition of G is a pair (X = {Xi | i ∈ I}, T ),
2

where each Xi is a subset of V which is called a bag, T is a tree with elements of I as nodes and satisfies
the following three properties.
S
1. i∈I Xi = V ,
2. for every edge {u, v} ∈ E, there is an index i ∈ I such that {u, v} ⊆ Xi ,
3. for all i, j, k ∈ I, if j lies on the path between i and k in T , then Xi ∩ Xk ⊆ Xj .
The width of a tree decomposition (X = {Xi | i ∈ I}, T ) equals max{|Xi | | i ∈ I} − 1. The
tree-width of a graph G, denoted by tw when G is clear from the context, is the minimum value of tw
such that G has a tree decomposition of width tw.
Definition 2.2. A tree decomposition (X = {Xi | i ∈ I}, T ) is called a nice tree decomposition, or N T
for short, if the following conditions are met:
1. Every bag of the tree has at most 2 children.
2. (JOIN bag) If a bag i has two children j and k, then Xi = Xj = Xk .
3. If a bag i has one child j, then one of the following conditions must hold:
(INTRODUCE bag) |Xi | = |Xj | + 1 and Xj ⊂ Xi
(FORGET bag) |Xi | = |Xj | − 1 and Xi ⊂ Xj
Lemma 2.3. ( [6]) Given a tree decomposition of a graph G with width tw, and n bags, one can find a
nice tree decomposition of G in linear time with width tw and O(n) bags.
Definition 2.4. A nice tree decomposition is called a very nice tree decomposition if each leaf bag
contains just a single vertex.
Definition 2.5. A very nice tree decomposition is called a standard very nice tree decomposition if each
bag an ordered set with tw + 1 elements, some of them can be null, and the position of each vertex in the
bags that it appears is alike.
Next, we review a compact representation for graphs of tree-width tw which is presented by Farzan
[11] and then use it to compact very nice tree decompositions. Given an unweighted, undirected, and unlabeled graph with n vertices that has a small tree-width tw, their representation provides space-efficient
encodings, or oracles, to perform degree, neighborhood, and adjacency queries in constant time in the
log n-bit word RAM model.
Lemma 2.6. ( [5]) A multiple parenthesis sequence with 2n parentheses of k types, in which the parentheses of any given type are balanced, can be represented using (2 + )n log k + o(n log k) bits to support
m-access, m-rank, m-select, m-findmatch and m-enclose in O(1) time, where m-access computes access
to the ith label in lexicographic order, m-rank computes the number of equivalent to m, m-select computes the position of the rth m and m-findmatch computes the matching closing (opening) parenthesis
and m-enclose(v, i) gives the position of the tightest open parenthesis of type i which encloses v.
For a graph G and its standard very nice tree decomposition with width tw, we modify the nice tree
decomposition as follow: First, we assume that all bags contain tw + 1 elements where some of them
might be null and assign types to all vertices in a top-down manner (e.g Figure 1b). Then, each bag is
labeled by a number i ranging from 1 to tw + 1. This label shows the position of each element in the bag
3

(a)

(b)

(c)

Figure 1: (a) A graph, (b) one of its standard very nice tree decomposition, (c) an ordered labeled tree.
which changed, but if a bag be same as its parent, the label of this bag set similarly like as the label of its
parent. In other cases, label of each bag is assigned as follow: For the vertices in the root give a vertex
type i if it has index i in this ordering. For a vertex v introduced in a bag X, define type(x) = j, where j
is the type of the vertex in the parent of X which has been replaced by v. Note that the only information
associated with each bag is the type of the vertex it introduces. So we can present the tree decomposition
as an ordered tree with a single label, not larger than tw + 1, on each bag. We assume the root introduces
tw + 1 vertices of different types, and to make representation easier separate them in a path of bags, with
labels 1 to tw + 1 (see Figure 1c).
To efficiently represent a very nice tree decomposition, we use Multiple Parenthesis (MP) structure
constructed as follow: Assume a preorder traversal of T , denoted by τp . In this traversal, when we enter
a bag, we add an open parenthesis followed by the label of the bag and when we leave a bag, we add a
close parenthesis accompanied by the label of bag. An example of a parenthesis sequence representation
for the tree of Figure 1c is shown in Figure 2.

Figure 2: Balanced parenthesis as shown in tree of Figure 1c.
Lemma 2.7. ( [14]) A balanced parenthesis sequence of size 2n, which is equivalent to an ordered
tree of size n, can be represented in 2n + o(n) bits, and support access(v), rank(v 0 , (0 ), select(v 0 , (0 ),
f indmatch(v), and child(i, v) operations in constant time.
In addition to storing the balanced parenthesis sequence, we need a table to store the edges of graph
G. Edge table is a matrix of dimension (tw + 1) × n which is filled by 0, 1 and “ ? ”. Each “ ? ” shows the
position of a vertex in the bags and each “1” shows an edge in graph G. For example, Table 1 shows edge
table of graph Figure 1a. The construction of this table with vertices sorted preorder from M P and extra
data structure are presented in [11] in details. Anyway, we use the MP sequence, the big table and other
data structures which are used in [11] to represent a graph with tree-width tw and to support queries in
constant time.

4

1
2
3

1
?
0
0

Table 1: Edge table.
4
3
2
5
(4,1) (3,1) (2,1)
0
?
(3,4)
?
(5,4)
0
?
(2,3)
?

In a graph G = (V, E), we define NGe (r) = {s ∈ E | s is incident to r in graph G} and the mixed
neighborhood of element r ∈ V ∪ E is denoted by NGmd (r) and is defined as {s ∈ V ∪ E | s is either
adjacent or incident to r in G}. Similarly, the closed neighborhood of v is denoted by NGmd [r] and equals
NGmd (r) ∪ {r}. A subset MD ⊆ V ∪ E is a mixed dominating set for G whenever for all r ∈ V ∪ E, we
have |NGmd [r] ∩ MD| ≥ 1. The mixed domination problem is to find a minimum sized mixed dominating
set for G and γm (G) denotes the minimum size among all mixed dominating sets of G.

3

Fundamental Concepts

The main idea we use to solve the mixed domination problem is to transform edge power to vertex
power, i.e. we transform domination power of edges to domination power for vertices. In this section,
we introduce some basic definitions which we use to solve the mixed domination problem.
Let MD be a mixed domination set for i ∈ I and v ∈ Xi . For edges and vertices in a bag, the rule of
transforming domination power of edges to vertices power is as follows:
• Power 2: If v ∈ MD, then the power of v is set equal to 2 and can dominate elements in NGmd [r],
• Power 1: If v ∈
/ MD but at least one of the incident edges of vertex v is in MD, then the power
of v is set equal to 1 and the vertex can dominate all its edges,
• Power 0: If v and none of its incident edges is not in MD, then the power of v is set equal to 0
and the vertex cannot dominate any edge or vertex.
A vertex v ∈ Xi has seven possible conditions according to v ∈ MD and covered by NGmd [v]. Table
2 illustrates. These seven states are respect to existing edges and vertices in a bag. The intuition behind
these cases is as follows:
1. For the first case; v and at least one of its edges belong to MD,
2. In the second case; v belong to MD however none of its edges belong to MD,
3. In the third case; v does not belong to MD but at least one of its incident edges belong to MD,
4. In the fourth case; v and all of its edges do not belong to MD, and v and its edges are dominated,
5. In the fifth case; v and all of its edges do not belong to MD, and v is not dominated but all its
edges are dominated,
6. In the sixth case; v and all of its edges do not belong to MD, and v is dominated but at least one
of its edges is not dominated,
7. In the seventh case; v and all of its edges do not belong to MD, and v and at least one of its edges
is not dominated.
5

Table 2: Conditions of each vertex respect to a bag.
1
2
3
4
5
6
7

v
v
v
v
v
v
v
v

∈ MD
∈ MD
∈ MD
∈
/ MD
∈
/ MD
∈
/ MD
∈
/ MD
∈
/ MD

NXe i (v) ∈ MD
∃u ∈ NXe i (v), uv ∈ MD
∀u ∈ NXe i (v), uv ∈
/ MD
∃u ∈ NXe i (v), uv ∈ MD
∀u ∈ NXe i (v), uv ∈
/ MD
∀u ∈ NXe i (v), uv ∈
/ MD
∀u ∈ NXe i (v), uv ∈
/ MD
∀u ∈ NXe i (v), uv ∈
/ MD

vertex cover
edge cover
vertex power illustration
v is covered
∀u ∈ NXe i (v), uv is covered
2
3a.
v is covered
∀u ∈ NXe i (v), uv is covered
2
3b.
v is covered
∀u ∈ NXe i (v), uv is covered
1
3c.
v is covered
∀u ∈ NXe i (v), uv is covered
0
3d.
v is not covered
∀u ∈ NXe i (v), uv is covered
0
3e.
v is covered
∃u ∈ NXe i (v), uv is not covered
0
3f.
v is not covered ∃u ∈ NXe i (v), uv is not covered
0
3g.

Figure 3 illustrates situations for an arbitrary vertex with respect to a bag. In these figures, each
rectangle indicates a bag and vertices or edges present in MD are drawn bold, not covered ones are
drawn by dotted lines or circles and the rest of them are covered.

(a) 1

(b) 2

(c) 3

(d) 4

(e) 5

(f) 6

(g) 7

Figure 3: Different situations for a vertex with respect to a bag.
Let T be a very nice tree decomposition for graph G, for each bag Xi in T , we define Xi4 as
Xi4 = {v ∈ V, such that v is in descendant bags of Xi , ∀i ∈ I}

(1)

and the induced subgraph af G with vertices Xi (or Xi4 ) as Gi (or G4
i ). Let MD be a mixed dominating
set for bag Xi and v ∈ Xi . For a vertex v, there are nine possible situations based on the intersection of
4
G4
i and bag Xi which are given in Table 3. By assume all element in Gi /Gi is dominated, seven states
of Table 3 is same as Table 2, but the edges exist in G4
i /Gi that are not dominated add two extra states
to possible states of v.
8. In the eighth case; v is dominated but at least one of its edges which exist in G4
i /Gi is not dominated,
9. In the ninth case; v and at least one of its edges which exist in G4
i /Gi are not dominated.
In both of states v does not belong to MD. In state 8, and In state 9, v is not dominated and at least one
of its incident edges which exist in G4
i /Gi is not dominated.
Table 3: Different cases for a vertex v ∈ Xi with respect to appeared edges and vertices in Xi .
v ∈ MD

NXe 4 (v) ∈ MD

1

v ∈ MD

∃u ∈

2

v ∈ MD

∀u ∈

3

v∈
/ MD

∃u ∈

4

v∈
/ MD

∀u ∈

5

v∈
/ MD

∀u ∈

6

v∈
/ MD

∀u ∈

7

v∈
/ MD

∀u ∈

8

v∈
/ MD

∀u ∈

9

v∈
/ MD

∀u ∈

i

NXe 4 (v), uv
i
NXe 4 (v), uv
i
NXe 4 (v), uv
i
NXe 4 (v), uv
i
NXe 4 (v), uv
i
NXe 4 (v), uv
i
NXe 4 (v), uv
i
NXe 4 (v), uv
i
NXe 4 (v), uv
i

vertex cover

edge is covered in this bag

edge is covered in previous bags

power

∈ MD

v is covered

2

Figure 4a

∈
/ MD

v is covered

2

Figure 4b

∈ MD

v is covered

∈
/ MD

v is covered

∈
/ MD

v is not covered

∀u ∈ NXe 4 (v), uv is covered
i
∀u ∈ NXe 4 (v), uv is covered
i
∀u ∈ NXe 4 (v), uv is covered
i
∀u ∈ NXe 4 (v), uv is covered
i
∀u ∈ NXe 4 (v), uv is covered
i
∀u ∈ NXe 4 (v), uv is covered
i
∀u ∈ NXe 4 (v), uv is covered
i
∃u ∈ NXe 4 (v), uv is not covered
i
∃u ∈ NXe 4 (v), uv is not covered
i

∈
/ MD

v is covered

∈
/ MD

v is not covered

∀u ∈ NXe i (v), uv is covered
∀u ∈ NXe i (v), uv is covered
∀u ∈ NXe i (v), uv is covered
∀u ∈ NXe i (v), uv is covered
∀u ∈ NXe i (v), uv is covered
∃u ∈ NXe i (v), uv is not covered
∃u ∈ NXe i (v), uv is not covered

∈
/ MD

v is covered

uv is or is not covered

∈
/ MD

v is not covered

uv is or is not covered

6

illustration

1

Figure 4c

0

Figure 4d

0

Figure 4e

0

Figure 4f

0

Figure 4g

0

Figure 4h

0

Figure 4i

(a) 1

(b) 2

(c) 3

(f) 6

(d) 4

(g) 7

(h) 8

(e) 5

(i) 9

Figure 4: Different cases for a vertex v ∈ Xi with respect to appeared edges and vertices in Xi .
Figure 4 is like Figure 3 except that it not only shows different situations for a vertex v ∈ Xi with
respect to a bag Xi , but also it considers appeared edges and vertices in previous bags.
For each edges, there are three different states possible: (1) The edge is in the mixed dominating set,
(2) it is not in the mixed dominating set, however it is covered by some element, or (3) it is not in the
mixed dominating set and it is also not covered by any element. These cases are summarized in Table 4.
Table 4: Possible condition for an edge
1
2
3

edge belongs to the mixed dominating set.
edge does not belong to mixed dominating set, but it is covered
edge is not in mixed dominating set and also is not covered.

We have two types of tables, one is the bag table denoted by Btablei which saves all possible states
for vertices and edges in the bag Xi which they can be in with respect to the elements of the bag (states
of Table 2) and another one is the status table which is denoted by Stablei and saves all possible states
for vertices and edges in the bag Xi which can be in with respect to not only in the bag Xi but also
with vertices and edges that appeared until now in G4
i . Each table is construct as follow: in Btablei
and Stablei each row represents a possible solution and each column corresponds to a vertex in Xi or
existing edges between the vertices of Xi and a cost value which shows the number of mixed domination
members in that row. The cells in each row of this table correspond to v0 , ..., vtw , e1 , ..., e(tw+1) , cost.
2

4

Proposed Algorithm

In this section, we present our algorithm to find the mixed domination number for a graph with bounded
tree-width. This algorithm is consisted of three phases:
Phase 1: Finding a very nice tree decomposition of G with width at most k. Let G = (V, E) be an unweighted and undirected graph with constant tree-width. We compute and then use a standard very
nice tree decomposition with width tw and then extract the sequence related to this decomposition
as is described in Section 2. Phase 1 can be computed in O(n) using Lemmas 2.3 and 2.6.
Phase 2: Traversing on the very nice tree decomposition obtained in the previous phase in a postorder manner and denoting the traversal by τdu . Traversal τdu begins from the leftmost leaf and then goes up
in the tree until it reaches the first join node and then goes to the leftmost leaf on the right subtree
of the join node recursively. It goes up if both children of the join node are visited and visits the
join node itself and continues until it reaches the root. This phase can be computed in O(n) time.

7

Phase 3: Traversing on τdu and updating corresponding tables for each bag as follow: whenever we reach a
leaf bag, we create a new table which contains the possible states that a node can have. In other
three cases, if a bag is an introduce or join bag, we combine the corresponding tables with each
other, and if the bag is a forget bag we construct the table to obtain all of the possible states that
vertices in this bag can have by considering edges and vertices which appeared heretofore.
It is clear that the time complexity of this phase relates to the time spend in processing each bag in
the traversal τdu .This process includes time to create a table for each leaf bag and combining two
tables for introduce, forget and join bags. A new table is created with tow rows, running in constant
time, therefore this operations add a constant time factor. To combine two tables we consider the
worst case. A row of table for a join or an introduce bag can be created in O(tw2 ) and for forget
bag it is O(tw). The worst case for join bag happens when they have all possible cases which leads
tw+1
2
to 9tw+1 × 3( 2 ) rows. Therefore, the time complexity of this phase equals O(9tw × 3tw × tw2 ).
The algorithm described so far is polynomial time which respect to the size of T , O(n), however it is
exponential with respect to the tree-width of T , tw. The following theorem states the time complexity of
our proposed algorithm.
2

Theorem 4.1. The running time of the describe approach is O(9tw × 3tw × tw2 × n).
Our proposed dynamic programming algorithm works on τdu which is the postorder traversal on a
very nice tree decomposition of G. When the algorithm visits a bag, it describes the partial solutions to
the mixed domination problem and as it continues to other bags, it extends the created partial solutions.
These partial solutions need to satisfy all of the problem specific constraints in G4
i except for the vertices
in Xi and their incident edges in G4
\G
.
The
status
tables
Stable
are
used
to
store
these partial solutions.
i
i
In other words, an Stable characterizes the partial solutions and each row in Stable contains a valid
assignment for vertices and edges in Gi .
To compute the Stable of each bag i, our algorithm uses Btable of the children of bag i. Since these
tables are computed bottom-up, the final solution of the mixed domination problem appears in the root of
T . So, it can be extracted by inspecting the table of the root. Algorithm 1 demonstrates how we achieve
the final answer γmd .
The algorithm 1 finds γmd by a postorder traversal of standard very nice tree decomposition of graph
and calls Algorithms 2, 3 and 4. Note that it is possible that combining two rows in different levels could
have created the same rows that we store the row with minimum cost in Stablei . To avoid searching and
sorting to find these repeated states, we use a coding to store created rows up to now. We use a helper
table in which each created row has a specific position in it. When a row is created while combining two
tables, the help table is checked and if there is a row with lower cost, then the lower cost is considered
and the help table is updated accordingly. Finally Algorithm 1 inspects the root table and finds γmd . To
illustrate the algorithm, consider the graph in Figure 5. The output of the algorithm is γmd = 2. Next we
describe how the tables are filled and partial solutions are computed.

Figure 5: Mixed domination

8

Algorithm 1 Our proposed algorithm to solve the mixed domination problem
INPUT: Preorder traversal on a standard very nice tree decomposition of graph G denoted by τdu .
OUTPUT: γmd for G.
for i ← 1 to |τdu | do
if Xi is a bag leaf then
Create a new table with two rows each corresponding to cases 2 and 5 for the isolated vertex in
Xi (see Section 4.1) .
else if Xi is an introduce bag then
for `1 ← 1 to number of rows in Stablei−1 do
for `2 ← 1 to number of rows in Btablei do
Call Algorithm 2 with inputs rStablei−1 (`1 , :) and rBtablei (`2 , :).
end for
end for
else if Xi is a forget bag then
for `1 ← 1 to number of rows in Stablei−1 do
Call Algorithm 3 with input rStablei−1 (`1 , :).
end for
else if Xi is a join bag then
for `1 ← 1 to number of rows in Stablei1 do
for `2 ← 1 to number of rows in Stablei2 do
Call Algorithm 4 with inputs rStablei1 (`1 , :) and rStablei2 (`2 , :).
end for
end for
end if
Add the created rows to Stablei .
end for

4.1

Table construction for leaf bags

During the traversal τdu , when we observe a leaf bag, a new table is created which saves all of the possible
states for the only vertex in that bag. Let Xi be a leaf bag, since we are working with a standard nice tree
decomposition, every leaf bag contains exactly one vertex. For vertex v ∈ Xi , the status table i denoted
as Stablei contains two rows. The first row corresponds to the situation in with vertex v belongs to an
optimal mixed domination set, and the last one is for the case in which vertex v does not belong to an
optimal mixed domination set. Therefore, this table has two rows where in the first row, the value of the
vertex is “2” by cost “1” , and in the second row, the value of the vertex is “5” by cost “0”.

4.2

Construction of the status table for an introduce bag

An introduce bag Xi has one more vertex than its child bag Xi−1 as well as the edges that are adjacent
with the new vertex and the vertices of the previous bag. Assume Stablei−1 contains all of the possible
states that can be occur up to this level for visited edges and vertices. After adding the new vertex and
the corresponding edges we need to add all of the new possible states to the new Stablei . To do so,
we compute Stablei as Stablei−1 ⊗ Btablei . Assume that n is the size of bag Xi , e is the number of
edges with both ends in Xi , rStablei−1 (`1 , :) and rBtablei (`2 , :) are two rows of Stablei−1 and Btablei , and
j references the entries of a row of a table. Then, Equation 2 describes the construction of the entries of

9

`th row of Stablei .


if 0 ≤ j ≤ tw .
rStablei−1 (`1 , j) ?Int rBtablei (`2 , j)

rStablei (`, j) = rStablei−1 (`1 , j) ∗Int rBtablei (`2 , j)
if tw + 1 ≤ j ≤ tw + tw+1
.
2



tw+1
rStablei−1 (`1 , j) + rBtablei (`2 , j) - |A| - |B|, if j = tw + 2 + 1 .

(2)

where
A = {α | (rStablei−1 (`1 , α) ≤ 2 ∧ rBtablei (`2 , α) ≤ 2) ∧ (0 ≤ α ≤ tw)}.


tw + 1
B = {α | (rStablei−1 (`1 , α) = 1 ∧ rBtablei (`2 , α) = 1) ∧ (tw + 1 ≤ α ≤ tw +
)}.
2

(3)
(4)

In Equation 2, two multiplication operators ?Int and ∗Int are used to compute the entries of Stablei . The
multiplication tables for those operators are given in Tables 5 and 6. Note that value “ − ” in Tables 5,
6, 7 and 8 never happen. The Algorithm 2 describes aforementioned approach in constructing rows of
Stablei in a formal manner.
Algorithms 2, 3 and 4 calculate the value of ` using Equation 5. After constructing an entire row in
Stablei , the value of ` is obtained as follow: Assume that (r0 , r1 , ..., rtw , rtw+1 , ..., rtw+(tw+1) , rtw+(tw+1)+1 )
2
2
is the output of the Algorithms, then number ` shows the number of a row that this output is saved in it.
Equation 5 shows how the value of ` is calculated. Array rHP is used to save entries of a row until the
value of ` is computed. If the `th row in Stablei is empty, the algorithm saves the output, however if the
`th row was filled, if the new rtw+(tw+1)+1 is less than the existing one, the algorithm replaces the value
2
of rtw+(tw+1)+1 .
2



tw+1
!
(
tw
2 )
X
 X


`=
ri × 9i + 
rtw+j × 4j−1  × 9tw+1 
(5)
i=0

j=1

Table 5: Multiplication operation for vertices in in- Table 6: Multiplication operation for edges in introduce bag
troduce bag
?Int
0
1
2
3
4
5
6
7

4.3

0
0
1
2
3
4
4,5
4,6
4,5,6,7

1
1
1
1
1
1
1
1

2
1
2
1
2
2
2
2

3 4
5
6
7
1 1
1
1
1
1 2
2
2
2
3 3
3
3
3
3 4
4
4
4
3 4
5
4
5
3 4,6 4,6 4,6 4,6
3 4,6 5,7 4,6 5,7

8
1
2
3
8
8
8
8

∗Int
0
1
2
3

9
1
2
3
8
9
8
9

0
0
1
2
2,3

1 2 3
- - 1 1 1
1 2 2
1 2 3

Construction of the status table for a forget bag

A forget bag Xi loses one vertex and its incident edges with respect to its present bag Xi−1 . So, it is
enough to omit the invalid rows from Stablei−1 to obtain the Stablei for bag Xi . Algorithm 3 describes
an approach for constructing rows of Stablei . This algorithm omits rows containing vertex v with values
5, 7, 8 and 9 and for other cases, updates the corresponding values.

10

Algorithm 2 Status table’s row construction algorithm for an introduce bag
INPUT: rStablei−1 (`1 , :) and rBtablei (`2 , :)
OUTPUT: rStablei (`, :)
c←0
for j ← 0 to tw do
if (rStablei−1 (`1 , j) ≤ 2) and (rBtablei (`2 , j) ≤ 2) then
c←c+1
end if
if |rStablei−1 (`1 , j) ?int rBtablei (`2 , j)| = 1 then
rHS (1, j) ← rStablei−1 (`1 , j) ?int rBtablei (`2 , j)
end if
end for

for j ← tw + 1 to tw + tw+1
do
2
if (rStablei−1 (`1 , j) = 1) and (rBtablei (`2 , j) = 1) then
c←c+1
end if
if |rStablei−1 (`1 , j) ∗Int rBtablei (`2 , j)| = 1 then
rHS (1, j) ← rStablei−1 (`1 , j) ∗Int rBtablei (`2 , j)
else
if for ej = vr vnew , Stablei−1 (`1 , r) ≤ 3 then
rHS (1, j) ← 2
else
rHS (1, j) ← 3
end if
end if
end for
for j ← 0 to tw do
if |rStablei−1 (`1 , j) ?int rBtablei (`2 , j)| = 2 then
if rStablei−1 (`1 , j) = 0 and rBtablei (`2 , j) = 5 then
if ∃wr ∈NBag
md (v ) , rHS (1, r) ≤ 2 then
j
rHS (1, j) ← 4
else
rHS (1, j) ← 5
end if
else
if ∀wr ∈NBag
md (v ),e =(w v ) , rStablei (s) ≤ 2 then
s
r j
j
rHS (1, j) ← firset element of rStablei−1 (`1 , j) ∗Int rBtablei (`2 , j)
else
rHS (1, j) ← second element of rStablei−1 (`1 , j) ∗Int rBtablei (`2 , j)
end if
end if
else
if ∀wr ∈NBag
md (v ),e =(w v ) , rHS (1, s) ≤ 2 and ∃w ∈N md (v ) , rHS (1, r) ≤ 2 then
s
r j
r
j
Bag j
rHS (1, j) ← 4
else if ∀wr ∈NBag
md (v ),e =(w v ) , rHS (1, s) ≤ 2 and ∀w ∈N md (v ) , rHS (1, r) ≥ 3 then
s
r j
r
j
Bag j
rHS (1, j) ← 5
11

else if ∃wr ∈NBag
md (v ),e =(w v ) , rHS (1, s) = 3 and ∃w ∈N md (v ) , rHS (1, r) ≤ 2 then
s
r j
r
j
Bag j
rHS (1, j) ← 6
else if ∃wr ∈NBag
md (v ),e =(w v ) , rHS (1, s) = 3 and ∀w ∈N md (v ) , rHS (1, r) ≥ 3 then
s
r j
r
j
Bag j
rHS (1, j) ← 7
end if
end if
end for
Calculate the value of `
rStablei (`, 1 : end − 1) ← rHS (1, 1 : end − 1)
if rStablei (`, end) > (rStablei−1 (`1 , end) + rBtablei (`2 , end) − c) then
rStablei (`, end) ← rStablei−1 (`1 , end) + rBtablei (`2 , end) − c
end if
Algorithm 3 Status table’s row construction algorithm for a forget bag
INPUT: rStablei−1 (`, :)
OUTPUT: rStablei (`, :) or 0
if (rStablei−1 (`, veliminated ) ≥ 7) or (rStablei−1 (`, veliminated ) = 5) then
Return 0
else
rHS (1, :) ← rStablei−1 (`, :)
if rStablei−1 (`, veliminated ) = 6 then
if (∀vr ∈NXmd (veliminated ),es =(vr ,veliminated ) , rStablei−1 (`, r) = 6) and (rStablei−1 (`, s) = 3) then
i−1

rHS (`, r) ← 8
else if (∀vr ∈NBag
md

i−1

(veliminated ),es =(vr ,veliminated ) , rStablei−1 (`, r)

= 7) and (rStablei−1 (`, s) = 3)

then
rHS (`, r) ← 9
end if
end if
end if
Calculate the value of `
rStablei (`, :) ← rHS (1, :)
rHS (`, veliminated ) ← 0
∀vr ∈NXmd (veliminated ),es =(vr ,veliminated ) , rHS (`, s) ← 0
i−1

4.4

Construction of the status table for a join bag

A join bag Xi has the same set of vertices and edges with its two children Xi1 and Xi2 . To construct
possible states for Xi in Stablei , we compute Stablei = Stablei1 ⊗ Stablei2 . Let rStablei1 (`1 , :) and
rStablei2 (`2 , :) are two rows of Stablei1 and Stablei2 , and j references the entries of a row of a table. Then
Equation 2 describes how to construct the rows of Stablei .


if 0 ≤ j ≤ tw .
rStablei1 (`1 , j) ?Join rStablei2 (`2 , j),

rStablei (`, j) = rStablei1 (`1 , j) ∗Join rStablei2 (`2 , j),
if tw + 1 ≤ i ≤ tw + tw+1
.
2



tw+1
rStablei1 (`1 , j) + rStablei2 (`2 , j) - |A| - |B|, if i = tw + 2 + 1 .
12

(6)

where
A = {α | (rStablei1 (`1 , α) ≤ 2 ∧ rStablei2 (`2 , α) ≤ 2) ∧ (0 ≤ α ≤ tw)} .


tw + 1
B = {α | (rStablei1 (`1 , α) = 1 ∧ rStablei2 (`2 , α) = 1) ∧ (tw + 1 ≤ α ≤ tw + 1 +
)}.
2

(7)
(8)

In Equation 6, two different multiplication operations ?Join and ∗Join are used to obtain the entries of
Stablei . Their multiplication tables are given in Tables 7 and 8. Algorithm 4 describes how to construct
the rows of Stablei precisely.
Table 7: Multiplication operation for vertices in join
bag
?Join
0
1
2
3
4
5

0 1 2
0 - - 1 1
- 1 2
- 1 1
- 1 2
- 1 2

3
1
1
3
3
3

4 5
- 1 1
2 2
3 3
4 4
4 5

6

-

1 2

3

4

4

7

-

1 2

3

4

5

8
9

-

1 2
1 2

3
3

8
8

8
9

6
1
2
3
4
4
First Second
4
6
First Second
4
6
8
8

7
1
2
3
4
5
First Second
4
6
First Second
5
7
8
9

8
1
2
3
8
8

Table 8: Multiplication operation for edges in Join
bag
9
1
2
3
8
9

∗Join
0
1
2
3

0
0
-

1
1
1
1

2
1
2
2

3
1
2
3

8 8
8 9
8 8
8 9

Note that Algorithm 1 compute γmd but not a minimum mixed dominating set. However, it is possible
to modify the algorithm to obtain a mixed dominating set with minimum size. This modification are as
follow. We first consider some fixed arbitrary one to one total numbering function φ used to code elements
1−1
of S. Let |V | = n and |E| = m, φ : {V ∪ E} −−→ {1, 2, ..., n + m} and ψ : φ(x) → {0, 1}.
Function φ determines an arbitrary order on set {V ∪ E}. So, we get elements in a particular order
to code partial solution. Indeed, we display a partial solution as a binary number, i.e. every element in
{V ∪ E} can have two values of 0 or 1 where 0 indicates that the corresponding element is not present in
the mixed domination set and 1 indicates its presence in the mixed dominating set. The function ψ is used
to convert a partial solution to a binary number. So, its enough to change the algorithm and save elements
of partial solution by a binary number just after constructing each state. Other changes to algorithm are

straight forward. Note that the maximum number of bits that can be changed in a state is equal k + k2 .

5

Correctness

In this section we first show that finding the mixed domination number of graphs is checkable in lineartime if the graph has bounded tree-width using the Courcelle’s theorem [9]. Then, we describe how to
ensure that our proposed bottom-up method solves the mixed domination problem by computing partial
solutions as state tables for bags. A partial solution is an object which stores all possible states for
vertices and edges in a bag. Therefore, what we need to prove is showing that how a partial solution can
be extended to a final solution.
To show that the mixed domination property of graphs can be checked in linear-time for graphs with
bounded tree-width, we consider the following to express mixed domination in monadic second-order
logic.
13

Algorithm 4 Status table’s row construction algorithm for a join bag
INPUT: rStablei1 (`1 , :) and rStablei2 (`2 , :)
OUTPUT: rStablei (`, :)
for j ← 0 to tw do
if |rStablei1 (`1 , j) ?Join rStablei2 (`2 , j)| = 1 then
rHS (1, j) ← rStablei1 (`1 , j) ?Join rStablei2 (`2 , j)
end if
if (rStablei1 (`1 , j) ≤ 2) and (rStablei (`2 , j) ≤ 2) then
c←c+1
end if
end for

for j ← tw to tw + tw+1
do
2
rHS (1, j) ← rStablei1 (`1 , j) ∗Join rStablei2 (`2 , j)
if (rStablei−1 (`1 , j) = 1) and (rStablei (`2 , j) = 1) then
c←c+1
end if
end for
for j ← 0 to tw do
if |rStablei1 (`1 , j) ?Join rStablei2 (`2 , j)| = 2 then
if ∀wr ∈NBag
md (v ),e =(w v ) , rHS (1, s) ≤ 2 then
s
r j
j
rHS (`, j) ← Firset element of rStablei1 (`1 , j) ∗Join rStablei2 (`2 , j)
else
rHS (1, j) ← Second element of rStablei1 (`1 , j) ∗Join rStablei2 (`2 , j)
end if
end if
end for
Calculate the value of `
rStablei (`, 1 : end − 1) ← rHS (1, 1 : end − 1)
if rStablei (`, end) > (rStablei−1 (end) + rBtablei (end) − c) then
rStablei (end) ← rStablei−1 (end) + rBtablei (end) − c
end if
• vertices, edges, sets of vertices and edges of a graph G as variables of monodic second order logic.
• Relations adj(p, q) and inc(p, q) which are defined as follows: adj(p, q) is a binary adjacency
relation and it is true if and only if p and q are two adjacent vertices or are two adjacent edges of G,
and inc(p, q) is a binary incidence relation and it is true if and only if edge p is incident to vertex q
or vertex p is incident to edge q.
• The set operations ∪, ∩, ⊆ and ∈ which denoted the union, the intersection, the subset and the
membership operators.
• Unary set cardinality operator |S| and the set equality operator =.
• The comparison operator ≤.
• The logical connectives AND (∧) and OR (∨).

14

• The logical quantifiers ∀ and ∃ over vertices, edges, sets of vertices and edges of G.
By modeling the mixed domination property of graphs in the described monadic second-order logic,
we can conclude that checking this property on graphs with a bounded tree-width is a linear time task.
Let G = (V, E) be a given simple graph. For any element r ∈ V ∪ E, the mixed neighborhood of r
is denoted by N md (r) and is defined as NGmd (r) = {s ∈ V ∪ E | adj(s, r) ∨ inc(s, r)} and the closed
neighborhood of r is denoted by NGmd [r] and equals NGmd [r] = NGmd (r) ∪ {r}. A subset S ⊆ V ∪ E is a
mixed dominating set (MDS) for G, if for all r ∈ V ∪ E, it is the case that |NGmd [r] ∩ S| ≥ 1. The mixed
domination number problem asks for the size of S which is expressed as in Equation 9:
∃S ⊆ (V ∪ E), S is an MDS ∧ ∀M ⊆ (V ∪ E), M is an MDS, |S| ≤ |M |.

(9)

To show correctness of our algorithm, it is enough to show that the extension of a partial solution
satisfies the condition of the restricted form of mixed domination problem. Extending a partial solution
begins by constructing a table for a leaf bag. At first, the leaf table contains two possible states (see
Section 4.1). Obviously, these two states are all possible states that can occur for a vertex in a bag.
According to the definition of the tree decomposition, a bag Xi is a separator whenever it separates
the vertices of (Xi4 )\Xi from V \(Xi4 ), so the vertices of (Xi4 )\Xi do not appear in other bags except
the ones descending from bag Xi . Hence, in our bottom-up approach, all of the possible states have been
considered for vertices of bag Xi since they will never be considered again. using this fact, we continue
the proof of correctness of our algorithm by first checking the extension of an introduce bag.
Lemma 5.1. Let Stablei−1 and Btablei be two tables with all possible states mentioned in Table 3 and
Table 2 for Xi−1 and Xi respectively. Combining these two tables according to Algorithm 1 produces all
of the possible states for bag Xi .
Proof. The proof is by contradiction. A new states state r ∈ Stablei is the result of multiplying two
possible states r1 ∈ Stablei−1 and r2 ∈ Btablei . We need to show that state r cannot be produced
by impossible states. Let r10 be a possible and r20 be an impossible state, hence r10 ∈ Stablei−1 and
r20 ∈
/ Btablei and r = r1 ⊗r2 . Since r is a possible state, then it preserve all of the restrictions of the mixed
/ Btablei does not satisfy those restrictions and is impossible. So,
domination problem while state r20 ∈
because we cannot satisfy some restrictions in the entire problem while for a part of it, it is not satisfied.
/ Btablei is
/ Stablei−1 and r20 ∈
/ Stablei−1 and r20 ∈ Btablei or r10 ∈
Similarly, the prof for cases r10 ∈
similar. So, combining Stablei−1 and Btablei produces all of the possible states for bag Xi .
In the second step we prof how extension of forget bag satisfy restriction mixed domination problem.
Lemma 5.2. Let Stablei−1 be a table with all possible states for bag Xi−1 . Deleting invalid rows from
this table produces all of the possible states for bag Xi .
Proof. Suppose that the vertex v is the forget vertex, thus it does not appear in later steps, all of its edges
have appeared up to now and all the its possible states are checked before constructing Stablei−1 . For
vertex v and its edges, there are four cases to consider:
1. vertex v and its edges are dominated: In these cases, the value of vertex v is either 1, 2, 3 or 4.
So, they are valid cases and remain in Stablei
2. vertex v is not dominated: For these cases, the value of v is either 5, 7 or 9. So, they are invalid
cases and are not allocated to appear in Stablei since no neighbor of vertex v appeared till now.

15

3. vertex v is dominated but at least one of its edges in G4
i−1 \Gi−1 is not dominated: Let e be an
4
edge in Gi−1 \Gi−1 which is not dominated. Edge e causes the value of vertex v to be 8 and makes
invalid cases. So, these cases must be omitted from Stablei since edge e has not any neighbor
which appeared till now.
4. vertex v and its edges in G4
i−1 \Gi−1 are dominated but at least one of its edges in Gi−1 is not
0
dominated: Let e = (v, v ) be an edge in Gi−1 that is not dominated. So, edge e causes that the
value of v to be 6. By deleting vertex v, edge e is converted to an external edge for bag i and does
not appear in Gi . However it is possible that an edge appears in later steps and dominated e, so this
states can be extended to a solution and we need to save it. So, we consider the effect of edge e on
vertex v 0 and change the value of vertex v 0 .

In the third step, we are going to check the correctness of our algorithm in the extension of a join bag.
Lemma 5.3. Let Stablei1 and Stablei2 be tables with all possible states mentioned in Table 3 and Table
2 for children of bag Xi . Combining these two tables produces all of the possible states for bag Xi .
Proof. The proof is by contradiction. The proof of correctness is similar to Lemma 5.1. With this
difference that r10 ∈ Stablei1 and r20 ∈
/ Stablei2 and for other cases similarly r10 ∈
/ Stablei1 and r20 ∈
Stablei2 and r10 ∈
/ Stablei1 and r20 ∈
/ Stablei2 .
Theorem 5.4. Our proposed mixed domination algorithm produces all possible states satisfying the
mixed domination problem.
Proof. A partial solution starts by considering a leaf bag and initializing the leaf table to contain all two
possible states. By Lemmas 5.1, 5.2 and 5.3, we proved that every extension of partial solutions contain
all of the possible states that satisfy the conditions of mixed domination problem, so, our algorithm
produces all possible states that satisfy mixed domination.
Lemma 5.5. Every extension of a partial solution preserves possible states with minimum cost.
Proof. The Algorithm 1 stores rows of Stablei using a coding scheme and updates the state with minimum cost. So, every extension of a partial solution preserves possible states with minimum cost.
Theorem 5.6. Our proposed dynamic algorithm computes γmd of graphs with constant tree-width in the
2
status table of root bag, e.g. Stableroot in O(9tw × 3tw × tw2 × n) time.
Proof. According to the Theorem 5.4 and Lemma 5.5, our algorithm preserves possible states with minimum cost in every bag, so Stableroot contains all of the possible states with minimum cost. To find γmd ,
it is enough for the algorithm to find the smallest cost among all of the possible states in the root bag.
Also Theorem 4.1 expresses the time complexity of this algorithm. So, the desired result is obtained.

6

Conclusion

Mixed domination problem has many applications in electric power systems. In this paper, we proposed a
novel algorithm to find the mixed dominating number of graphs with bounded tree-width. Our algorithm
used a novel technique of imputing edge domination power to vertices of graph. Using this technique
and by analyzing our algorithm, we have shown for the first time that the mixed domination problem is
16

fixed-parameter tractable. As a future work, we suggest to enhance the running time of our algorithm
for special classes of graphs. Studying other parameters for the mixed domination problem such as
path-width seems a fruitful topic, too. More importantly, exploiting our technique of imputing power to
vertices from edges to solve other graph problems is another research direction.

Acknowledgement
This article has been written while the second author was in a sabbatical visit to the University of Auckland. He would like to express his gratitude to Prof. Cristian S. Calude and his research group for the
nice and friendly hospitality.

References
[1] A DHAR , G. S., AND P ENG , S. Mixed domination in trees: a parallel algorithm. Congr. Numer 100
(1994), 73–80.
[2] A HANGAR , H. A., A SGHARSHARGHI , L., S HEIKHOLESLAMI , S., AND VOLKMANN , L. Signed
mixed roman domination numbers in graphs. Journal of Combinatorial Optimization (2015), 1–19.
[3] A HANGAR , H. A., H AYNES , T. W., AND VALENZUELA -T RIPODORO , J. Mixed roman domination in graphs. Bulletin of the Malaysian Mathematical Sciences Society (2015), 1–12.
[4] A LAVI , Y., B EHZAD , M., L ESNIAK -F OSTER , L. M., AND N ORDHAUS , E. Total matchings and
total coverings of graphs. Journal of Graph Theory 1, 2 (1977), 135–140.
[5] BARBAY, J., A LEARDI , L. C., H E , M., AND M UNRO , J. I. Succinct representation of labeled
graphs. In International Symposium on Algorithms and Computation (2007), Springer, pp. 316–
328.
[6] B ODLAENDER , H. L. A linear-time algorithm for finding tree-decompositions of small treewidth.
SIAM Journal on computing 25, 6 (1996), 1305–1317.
[7] B ODLAENDER , H. L., AND VAN A NTWERPEN - DE F LUITER , B. Reduction algorithms for graphs
of small treewidth. Information and Computation 167, 2 (2001), 86–119.
[8] C HIMANI , M., M UTZEL , P., AND Z EY, B. Improved steiner tree algorithms for bounded treewidth.
Journal of Discrete Algorithms 16 (2012), 67–78.
[9] C OURCELLE , B. The monadic second-order logic of graphs. I. recognizable sets of finite graphs.
Information and computation 85, 1 (1990), 12–75.
[10] C OURCELLE , B. Fly-automata for checking monadic second-order properties of graphs of bounded
tree-width. Electronic Notes in Discrete Mathematics 50 (2015), 3–8.
[11] FARZAN , A., AND K AMALI , S. Compact navigation and distance oracles for graphs with small
treewidth. Algorithmica 69, 1 (2014), 92–116.
[12] H ATAMI , P. An approximation algorithm for the total covering problem. Discussiones Mathematicae Graph Theory 27, 3 (2007), 553–558.
17

[13] H AYNES , T. W., H EDETNIEMI , S., AND S LATER , P. Fundamentals of domination in graphs. CRC
Press, 1998.
[14] H E , M., M UNRO , J. I., AND R AO , S. S. Succinct ordinal trees based on tree covering. In International Colloquium on Automata, Languages, and Programming (2007), Springer, pp. 509–520.
[15] L AN , J. K., AND C HANG , G. J. On the mixed domination problem in graphs. Theoretical Computer Science 476 (2013), 84–93.
[16] ROBERTSON , N., AND S EYMOUR , P. D. Graph minors. III. planar tree-width. Journal of Combinatorial Theory, Series B 36, 1 (1984), 49–64.
[17] W EST, D. B., ET AL . Introduction to graph theory, vol. 2. Prentice hall Upper Saddle River, 2001.
[18] Z HAO , Y., K ANG , L., AND S OHN , M. Y. The algorithmic complexity of mixed domination in
graphs. Theoretical Computer Science 412, 22 (2011), 2387–2392.

18

