# Constrained Connectivity in Bounded X-Width Multi-Interface Networks
## 1 Introduction
### Our Results  
In this paper, we are interested in the \(p\)-Coverage problem. In particular, each node of the network can activate at most \(p\) interfaces. In what follows, the \(p\)-Coverage problem will be denoted simply as _CMI(\(p\))_, in accordance to the name provided to the original formalization of the Coverage problem on multi-interface networks where no restrictions on the number of interfaces each device may activate was introduced, see [1]. Actually, we consider what was referred to as the _unbounded case_, in which instead there is no bound on the number \(k\) of interfaces available over all the network. Considering the new notation, that problem becomes _CMI(\(\infty\))_, i.e., \(p=\infty\). Moreover, following the trend of the previous work [2; 3] on the same subject (and similarly to the technique used in [19]), we focus on _CMI(2)_. The contribution of this paper is summarized and compared with previous results in Table 1.  
In particular, we investigate _CMI(2)_ on the class of graphs with bounded treewidth, showing that it is indeed polynomially solvable. Then, to obtain specific performance, we consider two well-known (but incomparable) subclasses of graphs with bounded treewidth that are graph admitting a bounded pathwidth or a bounded carvingwidth. While the formal definitions of treewidth, pathwidth and carvingwidth will be provided later, here we give just a first intuition of what kind of graphs we are approaching. \begin{table}
\begin{tabular}{l l l l} \hline \hline
**Graph Class** & **Costs** & **Complexity of _CMI(2)_** & **Reference** \\ \hline Graphs with \(\Delta\geq 4\) & unitary & NP-complete (feasibility) & [2] \\ Treewidth \(h\) & arbitrary & feasibility in poly-time regarding \(h\) & this paper \\ Carvingwidth \(h\) & arbitrary & optimally solvable in \(O(k^{4h}n)\) & this paper \\ Pathwidth \(h\) & arbitrary & optimally solvable in \(O(k^{2(h+1)}n)\) & this paper \\ Series-Parallel graphs & arbitrary & optimally solvable in \(O(k^{6}n)\) & [3] \\ Complete Bipartite graphs & arbitrary & optimally solvable in \(O(k^{4}n)\) & [2] \\ Complete graphs & arbitrary & optimally solvable in \(O(k^{3}n)\) & [2] \\ Rings & arbitrary & optimally solvable in \(O(k^{3}n)\) & [2] \\ Trees & arbitrary & optimally solvable in \(O(\Delta k^{2}n)\) & [2] \\ Paths & arbitrary & optimally solvable in \(O(kn)\) & [13] \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Complexity of the _CMI(2)_ problem. Parameters \(n\), \(k\), \(\Delta\) and \(h\) are the number of nodes, the number of interfaces, the maximum node degree, and the X-width of the input instance of _CMI(2)_, respectively. A _tree decomposition_ of a graph \(G\) is a tree of subsets of vertices of \(G\) such that the endpoints of each edge of \(G\) appear together in at least one subset and all subsets containing a same vertex of \(G\) constitute a connected subtree. The treewidth is one less than the size of the largest subset in a minimal tree decomposition. A _path decomposition_ of a graph \(G\) is a sequence (a path) of subsets of vertices of \(G\) such that the endpoints of each edge of \(G\) appear in at least one subset and each vertex of \(G\) appears in a contiguous subsequence of the subsets. The pathwidth is one less than the size of the largest subset in a minimal path decomposition. A _carving_ of a graph \(G\) is a tree \(T\) whose internal vertices all have degree 3 and whose leaves correspond to the vertices of \(G\). The _width_ of a carving \(T\) is the maximum size of an edge-cut in \(G\) that is induced by an edge of \(T\). The carvingwidth of \(G\) is the minimum width of a carving of \(G\). While graphs admitting bounded pathwidth or bounded carvingwidth also admit bounded treewidth, there is no relation among the two classes of graphs admitting bounded pathwidth and those of bounded carvingwidth. Hence, investigating on the resolution algorithms of _CMI(2)_ when restricted to one of the two subclasses is a challenging issue.