# Constrained Connectivity in Bounded X-Width Multi-Interface Networks
## 2 Notation and Definitions
Figure 4: A nice path decomposition of width 2 for the graph shown in Figure 2.

Figure 3: A path decomposition of width 2 for the graph shown in Figure 2.

In this case, we set \(f(X_{i},\mathcal{A})=+\infty\). Since in \(X_{1}\) there is only one vertex \(u\), in \(G(X_{1})\) there are no edges, and \(\mathcal{A}=\{A(u)\}\), the following condition holds:

* \(f(X_{1},\mathcal{A})=c(A(u))\) if \(|A(u)|\subseteq W(u)\), and \(|A(u)|\leq 2\). Substantially, for \(X_{1}\) we activate all the possible subsets of at most two interfaces available for \(u\). Actually, since in \(G(X_{1})\) there is only one vertex, these partial solutions are needed only to build an optimal solution for \(G\), if \(G\) contains more than one vertex. In any _introduce node_\(X_{i+1}=X_{i}\cup\{v\}\), the value \(f(X_{i+1},\mathcal{A})\), for a specific collection \(\mathcal{A}\) of active interface sets, is computed by solving the following constrained minimization problem, which uses the values \(f(X_{i},\mathcal{B})\) already computed in the previous node \(X_{i}\). \[ \begin{split}\min& f(X_{i},\mathcal{B})+c(A(v))\\ \text{s.t.}& B(u)=A(u)\quad\forall u\in X_{i}\\ & A(v)\cap B(u)\
eq\emptyset\quad\forall u\in X_{i}\cap N(v)\end{split}  \tag{1}\]

with \(N(v)\) being the set of vertices neighboring \(v\). The second constraint assures that the vertex \(v\) can communicate with all its adjacent vertices \(u\) in \(G(X_{i+1})\) by sharing at least a common active interface. The first constraint simply states that the new solution \(\mathcal{A}\) equals \(\mathcal{B}\) for all the vertices except the new one \(v\). The objective function sums the already computed optimum value \(f(X_{i},\mathcal{B})\) with the cost of the interfaces \(A(v)\) activated in the new vertex \(v\). In any _forget node_\(X_{i+1}=X_{i}\setminus\{v\}\), the value \(f(X_{i+1},\mathcal{A})\) for a specific collection of interface subsets \(A(u)\), with \(u\in X_{i}\), and \(|A(u)|\leq 2\) is computed by solving the following constrained minimization problem. \[ \begin{split}\min& f(X_{i},\mathcal{A}\cup B(v))\\ \text{s.t.}& A(u)\cap B(v)\
eq\emptyset\quad\forall u \in X_{i+1}\cap N(v)\\ & B(v)\subseteq W(v)\end{split}  \tag{2}\]

In fact, the value \(f(X_{i+1},\mathcal{A})\) is essentially the minimum value of \(f(X_{i},\mathcal{A}\cup B(v))\) for every possible subset of active interfaces \(B(v)\) compatible with every \(A(u)\), which means \(A(u)\cap B(v)\
eq\emptyset\) for every \(u\) adjacent to \(v\). At the end of the algorithm, the optimum of _CMI(2)_ is the minimum value \(f(X_{r},\mathcal{A})\), for every possible collection of interface subsets \(A(u)\subseteq W(u)\), with \(|A(u)|\leq 2\), in the unique vertex \(u\in X_{r}\). We conclude this section computing the complexity of the algorithm. At each _introduce node_, we solve at most \((k+\binom{k}{2})^{(k+1)}\) problems (1), one for every possible collection \(\mathcal{A}\). In fact, every possible subset of active interfaces \(A(u)\) is such that \(|A(u)|\leq 2\), and every \(|X_{i+1}|\leq h+1\). Moreover, for every possible collection \(\mathcal{A}\), since in each subproblem there are at most \(h+1\) constraints, its resolution requires \(O(h)=O(1)\) time. Analogously, at any _forget node_, we solve at most \((k+\binom{k}{2})^{(h+1)}\) problems (2), given by all the subsets of active interfaces \(A(u)\), with \(u\in X_{i+1}\), and all the possible subsets of active interfaces \(B(v)\) for the forget vertex \(v\). In conclusion, since there are at most \(n\)_introduce nodes_ and \(n\)_forget nodes_, the time complexity of the dynamic programming algorithm is \(O(n(k+\binom{k}{2})^{(h+1)})\). We can then state the following:

Theorem 4: _Given an instance of CMI(2) with a graph \(G\), and a pathwidth decomposition \(\mathcal{P}\) of width \(h\) for \(G\), CMI(2) is solvable \(O(n(k+\binom{k}{2})^{(h+1)})\) time._

## 5 Graphs with Bounded Carvingwidth

We start by formally define what the _carvingwidth_[24] of a graph is.