# Multilayer Backbones for Internet of Battlefield Things +
## 2 Formulation of the Problem  
A dominating set (DS) [22] of a graph (i.e., the set of _dominators_) is defined as a subset of the nodes with the property that the rest of the nodes are adjacent (i.e., 1-hop neighbors) from some dominator(s). If the network induced by the DS is additionally connected, then the DS is called connected DS (CDS). In the IoBT setting, we seek for minimum CDS (MCDS), i.e., CDS with minimum cardinality. We treat an IoBT network as a multilayer network, i.e., as a multilayer graph [5; 7]. We assume that there exist only bidirectional links (In principle, the paper ideas can be applied to networks with unidirectional links as well). A multilayer network comprised of \(n\) layers is a pair \((G^{ML},E^{ML})\), where \(G^{ML}=\{G^{i},i=1,\ldots,n\}\) is a set of networks \((G_{i},E_{i})\) (i.e., with \(G_{i}\) nodes and \(E_{i}\) links), 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\}\). Figure 1 illustrates such a network, where we can see a _layer_ of soldiers, a layer comprised by helicopters, the _intralayer_ links connecting \"nodes\" of the same layer, and _interlayer_ links connecting \"nodes\" belonging to different layers.  
Apparently, the requirement of calculating a CDS with minimum cardinality stems from scalability issues [3]. Additionally, from the discussion in Section 1 and in ([3] Section III.B), where \"...resilience and latency requirements for synthesizing a near-optimal network\" [3] are emphasized, we conclude that the more nodes with many interlayer links are included in our IoBT backbone the better it is. The inclusion of many nodes with \"a lot\" of interlayer links supports low-latency communication among layers; we can consider them as the hubs encountered in the literature on complex networks that reduce the \"degrees of separation\". Moreover, the existence within the backbone of many nodes with \"a lot\" of interlayer links, reduces the danger of partitioning among layers. Therefore, we provide Definition 1 for the problem of calculating a MCDS for IoBT networks, and establish its computational complexity (Proposition 1) in the centralized setting, closing a gap in the literature which is open since [5] and it was not dealt with in [23].  
**Definition 1** (Multilayer MCDS problem for IoBT).: _Solve the MCDS for a multilayer graph in a distributed manner, i.e., calculate the set MCDSML comprised by the minimum number of nodes with the following properties: (a) their induced subgraph is connected (with intra and/or inter-layer links) and the rest of the nodes are adjacent to one node (or more) belonging to MCDSML, (b) maximize the number of dominators with many interlayer links, (c) knowing only the \(k\)-hop neighborhood of each node; we work with \(k=2\) here. (Working with broader neighborhoods (i.e., \(k>2\)) would cause a severe broadcast storm problem [24] in order to acquire the topology deploying successive rounds of \"beacon\" messages)._  
In the rest of this section, we will investigate and establish the computational complexity of the centralized version of our problem for connected dominating sets. In particular, we will define the decision and optimization version of the examined problem, and then establish their complexities. The validity of these results for the case of connected dominating sets calculated in a distributed fashion is straightforward.