# Multilayer Backbones for Internet of Battlefield Things +
## 2 Formulation of the Problem
#### Multilayer minimum connected dominating set problem  
INSTANCE: A multilayer network consisting of \(n\) layers, i.e., a set of \(n\) pairs \((G_{i},E_{i})\), where \(G_{i}\) is the node set of a usual network and \(E_{i}\) is a set of edges, for \(1\leq i\leq n\), and a set of interlayer links \(E^{ML}=\{E_{i,j}\subseteq G_{i}\times G_{j};i,j\in\{1,\ldots,n\},i\
eq j\}\). QUESTION: What is the minimum cardinality dominating set for \((G^{ML},E^{ML})\), i.e., what is the minimum cardinality subset \(V^{\prime}\subseteq(\cup V_{i})\) such that for all \(u\in(\cup V_{i})-V^{\prime}\) there is some \(v_{j}\in(\cup V_{i})\) for which \((u,v_{j})\in((\cup E_{i})\cup E^{ML})\), and moreover the induced subgraph defined by \(V^{\prime}\) is connected? We can now proceed to establish the computational complexity of the second problem. Our proof method will also establish the complexity of the first problem as well. The result is described in Proposition 1, but firstly we remind some background on proving the computational complexity of problems. So, a problem is NP-complete if the following two conditions hold:  
* we can
* _either_ transform in polynomial-time a known NP-complete problem to the problem at hand ([25] p. 45), _or_
* prove that the problem at hand contains a known NP-complete problem as a special case ([25] p. 63, Section 3.2.1); this is called the \"restriction\" approach to proving NP-completeness. We will now construct the proof that the problem of finding a minimum connected dominating set for \((V,E_{i})\) is NP-complete. Recall that our problem is an _optimization_ problem, i.e., \"...finding the _minimum_ dominating set\". Proposition 1: _The Multilayer MDS problem is NP-complete._  
Proof: Our proof consists of three steps: (a) Transform the problem into a decision version, (b) Prove that it belongs to the class of NP problems. (c) Establish its NP-completeness complexity by following the \"restriction\" approach, i.e., by showing that our problem contains a known NP-complete problem as a special case. **[STEP 1]**. Transform our optimization problem into the decision version of the same problem.] Without violating the validity of the proof, we will work with the _decision_ version of the problem:  
_Given an integer \(k>0\), does our multilayer network contain a connected dominating set of cardinality equal to \(k\)?_  
Apparently, the smallest \(k\) for which the answer to the above problem is 'yes' is the size of the minimum connected dominating set of our multilayer network. From the perspective of computational complexity, the two problems are equivalent (see item (b1) above): With the use of binary search, we need to solve the decision version for \(O(log(|\cup_{i}G^{i}|))\) different values of \(k\), i.e., which is a polynomial time of searches. **[STEP 2]**. Proving that the decision problem belongs to the NP class.] The MULTILAYER CONNECTED DOMINATING SET PROBLEM is clearly in NP, as given a graph \((G^{ML},E^{ML})\), a set \(S\subseteq\cup_{i}G^{i}\) of nodes, and a number \(k\), we can test if \(S\) is a connected dominating set of \((G^{ML},E^{ML})\) of size \(k\) or less by first checking if its cardinality is less than or equal to \(k\) and then checking if every node in \((G^{ML},E^{ML})\) is either in \(S\) or adjacent to a node in \(S\). This process clearly takes polynomial time, i.e., \(O(|\cup_{i}G^{i}|+|\cup_{i}E^{i}|+|EM^{ML}|)\). Should we wish to check whether \(S\) is actually connected, we can resort to any polynomial-time algorithm, e.g., breadth/depth first search. Therefore, the MULTILAYER CONNECTED DOMINATING SET PROBLEM is indeed in NP. **[STEP 3]**. Proving that the decision problem contains a known NP-complete problem as a special case.] The third step of our proof involves proving that the MULTILAYER CONNECTED DOMINATING SET PROBLEM contains as a special case the problem of finding a connected dominating set for a single layer graph \(G(V,E)\)--a known NP-complete problem ([25] p. 190, Problem GT2). We state the following corollary:  
**Corollary 1**.