# Constrained Connectivity in Bounded X-Width Multi-Interface Networks
## 2 Notation and Definitions
Notice that each internal node as exactly two children, and in a perfect binary tree there are \(2n-1\) nodes, then \(T\) has at most \(2n-1\) nodes. Concluding, the dynamic programming algorithm to solve _CMI(2)_ for a graph with carvingwidth \(h\) needs \(O((2n-1)k^{4h})\) time. We can then state the following:

Theorem 4.1: _Given an instance of CMI(2) with a graph \(G\), and a carvingwidth decomposition \(\mathcal{P}\) of width \(h\) for \(G\), CMI(2) is solvable \(O(nk^{4h})\) time._

## 6 Conclusions

In the context of multi-interface networks, we have investigated a constrained variant of the Coverage problem. Given a graph \(G=(V,E)\), the aim is to find the cheapest way to establish all the connections defined by \(E\) by activating for each node \(v\in V\) a suitable subset of interfaces among those available in \(v\). One further constraint provided as a positive integer \(p\) has been considered with respect to the original model. Parameter \(p\) specifies how many interfaces a single node can activate at most. The aim of the modification has been to balance the energy consumption among all the nodes of the network, hence prolonging the lifespan of the single nodes. As _CMI(\(p\))_ has been proven be much more difficult in general with respect to the basic case of _CMI_(\(\infty\)), we keep on investigating whether the problem can be efficiently solved when restricted to specific graph classes. In particular, we have considered graphs with bounded treewidth in general, and graphs with bounded pathwidth or bounded carvingwidth in particular. In these two subcases we could design optimal polynomial time algorithms to solve _CMI(2)_. All the results can be easily extended to _CMI(\(p\))_ of any constant \(p\geq 1\). As general main open question on _CMI(\(p\))_, it would be interesting to investigate general graphs in case the input instance is guaranteed to admit a solution, i.e., the complexity of the problem cannot rely on feasibility issues. Moreover, since the completeness proof for the underlying decisional problem holds for graphs with \(\Delta\geq 4\), while the problem has been solved for \(\Delta\leq 2\) (that is, paths and rings [2]), it remains to show what happens for sub-cubic graphs, i.e., \(\Delta\leq 3\). Other directions require investigation into whether _CMI(\(p\))_ can be solved on specific graph classes by means of different techniques. Please note that the solutions proposed for the case \(p=2\) can be easily extended to any \(p>2\); however, it is worth investigating whether _CMI(\(p\))_ can be solved on specific graph classes in a smarter way. Finally, a generalization of the problem that could cover more realistic cases, is to introduce multi-objective functions, similar to [26], where it is taken into account also global cost constraints. What can be done, for instance, if the underlying graph exhibits specific properties like small-world [27], planarity [28], or a bounded chromatic number [29; 30]? How would the problem be affected if the cost function determining the energy spent to activate an interface is related to the bandwidth or to the physical distance among connected devices (see [31])? All such possible investigating directions confirm the general and interdisciplinary nature of the multi-interface networks model. **Author Contributions:** Conceptualization, A.A. and A.N. ; Methodology, A.A. and A.N. ; Software, A.A. and A.N. ; Validation, A.A. and A.N. ; Formal analysis, A.A. and A.N. ; Investigation, A.A. and A.N. ; Resources, A.A. and A.N. ; Data curation, A.A. and A.N. ; Writing--original draft preparation, A.A. and A.N. ; Writing--review and editing, A.A. and A.N. ; Visualization, A.N. ; Supervision, A.N. ; Project administration, A.A. and A.N. ; Funding acquisition, A.A. and A.N. All authors have read and agreed to the published version of the manuscript. **Funding:** This work has been partially supported by the European project \"Geospatial based Environment for Optimization Systems Addressing Fire Emergencies\" (GEO-SAFE), contract no.