# Constrained Connectivity in Bounded X-Width Multi-Interface Networks
## 2 Notation and Definitions
If \(i\) is a leaf corresponding to a vertex \(u\in V\), then the following condition holds:
* \(f(i,\mathcal{A})=c(A(u))\). In fact, \(f(i,\mathcal{A})\) is essentially the cost of the active interfaces on the unique vertex \(u\) belonging to the subgraph \(G(i)\). If \(i\) is an internal node of \(T\) with two children \(j\) and \(k\), then we compute \(f(i,\mathcal{A})\) solving the following minimization problem, where \(\mathcal{A}\) has several subsets equal to \(|(V_{i},V_{-i})|\), as defined in Equation (3). Moreover, there can be edges between \(G(j)\) and \(G(l)\). If it is the case, the interfaces active on the extremes of these edges must be compatible. The following constrained minimization problem solves \(f(i,\mathcal{A})\) for a particular collection \(\mathcal{A}\) by using the values \(f(j,\mathcal{B})\), and \(f(k,\mathcal{C})\) already computed, with \(\mathcal{B}\) and \(\mathcal{C}\) being the collections defined according to Equation (3). \[ \begin{split}\min& f(j,\mathcal{B})+f(l,\mathcal{C})\\ \text{s.t.}& A(u)=B(u)\quad\forall u\in V_{i},(u,v) \in((V_{j},V_{j^{-}})\bigtriangleup(V_{i},V_{l^{-}}))\\ & A(u)=C(u)\quad\forall u\in V_{l},(u,v)\in((V_{j},V_{j^{-}}) \bigtriangleup(V_{l},V_{l^{-}}))\\ & B(u)\cap C(v)\
eq\emptyset\quad\forall u,v)\in((V_{j},V_{j^{-} })\cap(V_{l},V_{l^{-}}))\end{split}  \tag{4}\]

In fact, by definition of carving decomposition, we have that \(V_{i}=V_{j}\cup V_{l}\), \(V_{j}\cap V_{l}=\emptyset\), and that the edges in \((V_{i},V_{i^{-}})\) are the ones in \((V_{j},V_{j^{-}})\cup(V_{l},V_{l^{-}})\) minus the ones in \((V_{j},V_{j^{-}})\cap(V_{l},V_{l^{-}})\), i.e., \((V_{j},V_{j^{-}})\bigtriangleup(V_{l},V_{l^{-}})\). This means that the collection \(\mathcal{A}\) is bipartitioned into two sub-collections, one belonging to \(\mathcal{B}\), and the other belonging to \(\mathcal{C}\). The former refers the vertices in \(V_{j}\) that are extremes of some edges in \((V_{i},V_{i^{-}})\), the latter, analogously, refers the vertices in \(V_{l}\) that are extremes of some edges in \((V_{i},V_{i^{-}})\). This bi-partition leads to the first two constraints in Equation (4), while the third constraint guarantees the compatibility between every couple of subsets \(A(u)\), and \(A(v)\) in \(\mathcal{A}\) such that the edge \((u,v)\) belongs to \(G(i)\). Notice that \(\mathcal{A}=\emptyset\) for \(f(root,\mathcal{A})\), because \(V_{root^{-}}\) is empty, so there are no edges in \((V_{root},V_{root^{-}})\). This means that the last problem of the algorithm is the following. \[ \begin{split}\min& f(j,\mathcal{B})+f(l,\mathcal{C})\\ \text{s.t.}& B(u)\cap C(v)\
eq\emptyset\quad\forall(u,v )\in((V_{j},V_{j^{-}})\cap(V_{l},V_{l^{-}}))\end{split}  \tag{5}\]

where only the constraint that guarantees the compatibility of the two solutions \(\mathcal{B}\) and \(\mathcal{C}\) is needed. Clearly, the optimum of _CMI(2)_ in \(G\) is the value of \(f(root,\mathcal{A})\), which is unique, because \(\mathcal{A}\) is empty. The computational time needed to compute \(f(i,\mathcal{A})\) for a leaf of \(T\) is \(k+k^{2}\), i.e., \(\mathcal{O}(k^{2})\), because \(|\mathcal{A}|=1\), and we essentially try every subset of at most two interfaces for the unique vertex in \(V_{i}\). When \(i\) is an internal node of \(T\) with two children \(j\), and \(l\), we can just combine every collection \(\mathcal{B}\) with every collection \(\mathcal{C}\) in order to build \(\mathcal{A}\), and compute \(f(i,\mathcal{A})\). Given two collections \(\mathcal{B}\) and \(\mathcal{C}\), the check of the feasibility according to Equation (4) costs \(O(1)\) since there are at most \(O(1)\) edges between \(G(j)\) and \(G(l)\) that require activation. Moreover, as the cardinality of \(\mathcal{B}\) and of \(\mathcal{C}\) is at most \(h\), every set \(B(u)\in\mathcal{B}\) and every set \(C(u)\in\mathcal{C}\) contain at most two interfaces, the time complexity to compute \(f(i,\mathcal{A})\) for an internal node is \(O(k^{4h})\).