## 2 The Maximum Weighted Disjoint Dominating Sets Problem  
Let \(G=(V,E,\text{lifetime})\) be a simple, undirected, node-weighted graph, where \(V\) (with \(|V|=n\)) is the set of nodes, \(E\subseteq V\times V\) (with \(|E|=m\)) is the set of edges, and \(\text{lifetime}:V\to\mathbb{R}^{+}\) is a weight function that assigns a positive weight value \(\text{lifetime}(v)>0\) to each node \(v\in V\). Note that such a graph may represent the communication graph of a WSN, and the node weight may represent the lifetime of the node. However, before technically introducing the MWDDS problem, let us briefly recall some basic definitions and notations used throughout this paper. For more details on graph theoretic aspects, the readers may refer to [24]. We say that two nodes \(v\
eq u\in V\) are neighbors (adjacent to each other) if and only if there exists an edge between them, that is, \((v,u)\in E\). Given a node \(v\in V\), \(N(v):=\{u\in V\mid(v,u)\in E\}\) denotes the set of neighbors of \(v\), known as the open neighborhood of \(v\) in \(G\). Furthermore, the closed neighborhood of a node \(v\in V\), denoted by \(N[v]\), contains the nodes adjacent to \(v\) plus node \(v\) itself, that is, \(N[v]:=N(v)\cup\{v\}\). The degree \(\deg(v)\) of \(v\) is the number of neighbors of \(v\), that is, \(\deg(v):=|N(v)|\). More generally, given a subset of nodes \(D\subseteq V\), the open neighborhood of \(D\) denoted by \(N(D)\) is defined as \(\bigcup_{v\in D}N(v)\) and its closed neighborhood, denoted by \(N[D]\), is defined as \(N[D]:=N(D)\cup D\). **Definition 1** (Dominating set). : _A subset \(D\subseteq V\) of the nodes of a simple, undirected graph \(G=(V,E)\) is called a dominating set of \(G\) if and only if each node \(v\in V\setminus D\) has at least one neighbor in \(D\). Each node in a dominating set \(D\) is called a dominator, otherwise it is called a dominate. A dominator dominates (covers) itself and all its neighbors._  
Note, for example, that--given a simple, undirected graph \(G=(V,E)\)--the complete set of nodes (\(V\)) is a dominating set. **Definition 2** (Domatic partition). : _A set \(\mathcal{D}=\{D_{1},D_{2},\cdots,D_{k}\}\) of subsets \(D_{i}\subseteq V\) is called a domatic partition of a simple, undirected graph \(G=(V,E)\), if each \(D_{i}\) (\(i=1,\ldots,k\)) is a dominating set of \(G\) and all sets of \(\mathcal{D}\) are pairwise disjoint, which is the case if for all \(1\leq i<j\leq k\) it holds that \(D_{i}\cap D_{j}=\emptyset\)._  
**Definition 3** (Domatic number). : _The domatic number of a simple, undirected graph \(G=(V,E)\) is determined as \(|\mathcal{D}^{*}|\) where \(\mathcal{D}^{*}:=\text{argmax}\{|\mathcal{D}|\mid\mathcal{D}\text{ is a domatic partition of }G\}\). In other words, the domatic number of \(G\) is the size of the largest domatic partition of \(G\). It is known that the domatic number of a graph \(G\) is limited from above by \(\delta+1\), where \(\delta\) is the minimum degree of the nodes in \(V\)._Given a simple, undirected graph \(G=(V,E)\), the maximum disjoint dominating sets (MDDS) problem requires to find a domatic partition of \(G\) of maximal size. Furthermore, given a graph \(G=(V,E,\textit{lifetime})\) as introduced above, the maximum weighted disjoint dominating sets (MWDDS) problem is defined as follows. Any domatic partition \(\mathcal{D}\) of \(G\) is a valid solution. The objective function value of a valid solution \(\mathcal{D}=\{D_{1},\ldots,D_{|\mathcal{D}|}\}\) is defined as \(f(\mathcal{D}):=\sum_{i=1}^{|\mathcal{D}|}\min\{\textit{lifetime}(v)\mid v\in D _{i}\}\). In other words, the quality of a subset \(D_{i}\) is determined as the minimum lifetime of all its nodes. The objective is to find a valid solution \(\mathcal{D}^{*}\) that maximizes \(f()\).