# Constrained Connectivity in Bounded X-Width Multi-Interface Networks
## 2 Notation and Definitions
: _A path decomposition of a graph \(G=(V,E)\) is a set \(\mathcal{P}=(X_{1},\ldots,X_{r})\) of subsets of \(V\) that is \(X_{i}\subseteq V\) for each \(i\in\{1,\ldots,r\}\), called bags, such that_

* (i) for every \(u\in V\) there exists \(i\in\{1,\ldots,r\}\) with \(u\in X_{i}\);
* (ii) for every \((u,v)\in E\), there exists \(i\in\{1,\ldots,r\}\) with \(u,v\in X_{i}\);
* (iii) for every three bags \(X_{i}\), \(X_{j}\), and \(X_{k}\), with \(i\leq j\leq k\), it holds that \(X_{i}\cap X_{k}\subseteq X_{j}\). The _width_ of a path decomposition \(\mathcal{P}\) is the maximum number of vertices contained in every bag of \(\mathcal{P}\) minus one, i.e., \(\max_{i\in\{1,\ldots,r\}}|X_{i}|-1\). The _pathwidth_ of a graph \(G\), is the minimum width for every possible path decomposition of \(G\). For any fixed constant \(h\), if \(G\) has pathwidth at most \(h\) then \(G\) is said to be of _bounded pathwidth_. In the following, we will call nodes the elements of \(\mathcal{P}\), and vertices the elements of \(V\), to avoid confusions. An important property of path decomposition [20], which we exploit to write our dynamic programming algorithm, is the _pathwidth separator_ property. It states that for every three nodes \(X_{i}\), \(X_{j}\), and \(X_{k}\) such that \(X_{j}\) is between \(X_{i}\) and \(X_{k}\), each path in \(G\) that connects a vertex in \(X_{i}\setminus X_{j}\) with a vertex in \(X_{k}\setminus X_{j}\) contains a vertex in \(X_{j}\). This means that node \(X_{j}\) separates the vertices in \(X_{i}\setminus X_{j}\) from the ones in \(X_{k}\setminus X_{j}\). Our algorithm works on a particular type of path decomposition called _nice._ A nice path decomposition can be always obtained from a path decomposition in linear time, maintaining the same width. **Definition 4** ([20]). : _A path decomposition of a graph \(G=(V,E)\) is nice if \(|X_{1}|=|X_{r}|=1\), and for every \(i\in\{1,2,\ldots,r-1\}\) there is a vertex \(v\in V\), such that either \(X_{i+1}=X_{i}\cup\{v\}\) (introduce node), or \(X_{i+1}=X_{i}\setminus\{v\}\) (forget node)._

It is easy to check that the number of nodes in a nice path decomposition is at most twice the number of vertices in \(V\), because property (iii) in Definition 3 says that every vertex \(v\in V\) belongs to a consecutive set of bags. A path decomposition of the graph in Figure 2 is depicted in Figure 3, while a nice path decomposition, of the same graph, can be found in Figure 4. Both decompositions have width equal to 2. ### Solving CMI(2) on Graphs with Bounded Pathwidth

This section describes a polynomial time optimal algorithm for _CMI(2)_ on graphs with bounded pathwidth, which uses the dynamic programming technique. The algorithm exploits the nice path decomposition provided above, and in particular the pathwidth separator property. Given an instance of _CMI(2)_, it is possible in linear time [22; 23] to find a pathwidth decomposition for \(G(V,E)\) of width \(h\). Then, the algorithm computes a nice path decomposition \(\mathcal{P}=(X_{1},\ldots,X_{r})\) with the same width \(h\), which can be done again in linear time [20]. Denote by \(G(X_{i})\) the subgraph induced by the vertices in \(\bigcup_{j=1}^{i}X_{j}\). Let \(f(X_{i},\mathcal{A})\) be the minimum value of _CMI(2)_ on \(G(X_{i})\), where \(\mathcal{A}\) is a collection of \(|X_{i}|\) subsets \(A(u)\) of the available interfaces \(W(u)\), with \(u\in X_{i}\), which satisfies the following constraints. * The interfaces _active_ in the vertex \(u\) are those in \(A(u)\), with \(|A(u)|\leq 2\), for every \(u\in X_{i}\). By exploiting the pathwidth separator property, the core of the algorithm computes at each node \(X_{i}\) of \(\mathcal{P}\) the values \(f(X_{i},\mathcal{A})\), for every possible collection \(\mathcal{A}\). The dynamic programming algorithm starts at \(X_{1}\), and ends at \(X_{r}\). Clearly, the constrained version of _CMI(2)_ cannot be always solvable.