# Constrained Connectivity in Bounded X-Width Multi-Interface Networks
## 2 Notation and Definitions  
Given a graph \(G=(V,E)\), let \(V\) be the set of nodes, and \(E\) be the set of edge. Moreover, let \(n=|V|\) and \(m=|E|\). Unless differently specified, \(G\) is assumed to be simple (without multiple edges nor self-loops), undirected and connected. For each node \(v\in V\), we denote by \(\deg(v)\) the degree of \(v\), and let \(\Delta=\max_{v\in V}\deg(v)\). A global assignment of the interfaces to the nodes in \(V\) is given in terms of an appropriate interface assignment function \(W\), as follows. **Definition 1**. : _A function \(W\colon V\to 2^{\{1,2,\ldots,k\}}\) is said to cover graph \(G\) if for each \(\{u,v\}\in E\) we have \(W(u)\cap W(v)\
eq\emptyset\)._  
For all nodes in \(V\), the activation of a specific interface is assumed to cost the same. The rationale behind it is that each device might be thought to spend the same percentage of its energy. Hence, the costs associated with the interfaces are defined by a function \(c\colon\{1,\ldots,k\}\to\mathbb{R}_{+}\), and the cost of activating interface \(i\) is referred to as \(c_{i}\). The considered _CMI(p)_ optimization problem is so formulated:```
Input: A graph \(G=(V,E)\), an allocation of available interfaces \(W\colon V\to 2^{\{1,\ldots,k\}}\) covering graph \(G\), an interface cost function \(c\colon\{1,\ldots,k\}\to\mathbb{R}_{+}\), an integer \(p\geq 1\). Solution: If possible, an allocation of active interfaces \(W_{A}\colon V\to 2^{\{1,\ldots,k\}}\) covering \(G\) such that for all \(v\in V\), \(W_{A}(v)\subseteq W(v)\) and \(|W_{A}(v)|\leq p\); Otherwise, a negative answer. Goal: Minimize the total cost of the interfaces that are activated, i.e., \(c(W_{A})=\sum_{v\in V}\sum_{i\in W_{A}(v)}c_{i}\). ```

**Algorithm 1**_CMI(p)_: Coverage in Multi-Interface Networks

In general, the cost function \(c\) spans over \(\mathbb{R}^{+}\). When \(c(i)=1\), for any \(i=1\), \(\ldots\), \(k\) then the particular case of _unitary cost_ is considered. Clearly \(k\geq 2\) is always assumed as the case \(k=1\) admits the obvious and unique solution where all the nodes activate the only available interface. Please note that _CMI(p)_ is a generalization of the original _CMI(\(\infty\))_ problem (see [1,7]), where each node cannot activate more than \(p\) interfaces. Surprisingly, the basic case for \(p=2\) comes out to be more difficult, in general, than _CMI(\(\infty\))_. In fact, in [2] the following theorem has been proved:

Theorem 1 ([2]): _Finding a feasible solution for CMI(2) is NP-complete for graphs with \(\Delta\geq 4\), even for the unitary cost case._

Please note that the feasibility of _CMI(\(\infty\))_ is easily solvable by the definition of the problem. In fact, by activating all interfaces for each node, a feasible solution for _CMI(\(\infty\))_ is obtained. However, there are special graph classes that turn out to be much more affordable in _CMI(2)_. Concerning trees and complete graphs, for instance, in [2] the _CMI(\(\infty\))_ problem has been investigated. For trees _CMI(\(\infty\))_ comes out to be _APX_-hard whereas for complete graphs it is not approximable within \(O(\log k)\). In both topologies, instead, _CMI(2)_ is optimally solvable in polynomial time. In the next section, we show that _CMI(2)_ is polynomially solvable in graphs of bounded treewidth, whereas the subsequent sections explore in more details _CMI(2)_ in two different and incomparable graph classes, i.e., graphs with bounded pathwidth and graphs with bounded carvingwidth. ## 3 Graphs with Bounded Treewidth

In this section, we show that _CMI(2)_ is polynomially solvable in graphs of bounded treewidth. We start by formally define what the _treewidth_ of a graph is. A tree decomposition of a graph \(G\) is a way of representing \(G\) as a tree-like structure.