# Constrained Connectivity in Bounded X-Width Multi-Interface Networks
## 2 Notation and Definitions
Subsequently, we present our new resolution algorithm that optimally solves _CMI(2)_ on graphs with bounded carvingwidth in polynomial time. ### Definition of Carvingwidth

We briefly recall some basic definitions before describing the algorithm. Given a graph \(G=(V,E)\), let \(\{V_{1},V_{2}\}\) be a partition of \(V\), and \((V_{1},V_{2})\subseteq E\) be the subset of edges with one extreme in \(V_{1}\) and the other in \(V_{2}\). Clearly, \((V_{1},V_{2})\) is an edge-cut of \(G\). Let \(T\) be a sub-cubic tree where each leaf corresponds to one vertex in \(V\), and all the internal nodes have degree three (two children). For this particular tree, it is possible to define a specific edge-weight in the following way. For every edge \(e\in E(T)\), let \(T_{1}\) and \(T_{2}\) be the two subtrees obtained removing \(e\) from \(T\). Then, let \(V_{1}\) and \(V_{2}\) be the sets of vertices in \(V\) corresponding to the leaves in \(T_{1}\) and in \(T_{2}\). We set the weight \(w(e)\) of \(e\) at \(|(V_{1},V_{2})|\), i.e., the number of edges between \(V_{1}\) and \(V_{2}\). The tree \(T\) is called a _carving_ of \(G\), and \((T,w)\) is called a _carving decomposition_ of \(G\). The width of \((T,w)\) is the maximum weight \(w(e)\) overall \(e\in E(T)\). The _carvingwidth_ of \(G\), denoted by \(cw(G)\), is the minimum width over all carving decompositions of \(G\). For any fixed constant \(h\), if \(G\) has carvingwidth at most \(h\) then \(G\) is said to be of _bounded carvingwidth_. We define \(cw(G)=0\) if \(|V|=1\). An example of a carving decomposition for the graph in Figure 5 is shown in Figure 6, where the red (additional) edges among the leaves correspond to the edges of the decomposed graph. Each (black) edge of the tree is associated with an integer that is the weight given by the decomposition. The width of this particular carving decomposition is \(5\), which is the maximum of the weights, and corresponds to the cut \((\{1,2,5,6,7\},\{3,4\})\). ### Solving CMI(2) on Graphs with Bounded Carvingwidth

This section describes a polynomial time optimal algorithm for _CMI(2)_ on graphs with bounded carvingwidth, which uses the dynamic programming technique. Given an instance of _CMI(2)_, it is possible in linear time [23; 25] to find a carvingwidth decomposition \((T,w)\) for \(G(V,E)\) of width \(h\). Denote by _root_ the root of \(T\). We now describe a dynamic programming algorithm to find an optimal solution for _CMI(2)_ for \(G\), which exploits the structure and the properties of carving decomposition \((T,w)\). As already done

Figure 5: A sample graph admitting the carving decomposition in Figure 6.

Figure 6: A carving decomposition of width \(5\) for the graph shown in Figure 5.

before for the pathwidth, we will call nodes the vertices of \(T\), to avoid ambiguities between the vertices of the graph and those of \(T\). Denote by \(T(i)\) the subtree induced by the node \(i\) of \(T\) and all its descendants. Denote also by \(V_{i}\) the leaves of \(T(i)\), by \(V_{i^{-}}\) the leaves of \(T\) in \(V\setminus V_{i}\), and by \(G(i)\) the subgraph of \(G\) induced by the vertices in \(V_{i}\). In the core of the dynamic programming algorithm, we compute the optimal value of a constrained version of _CMI(2)_ restricted to the subgraph \(G(i)\). The constraint is given by the interfaces active on each node in \(V_{i}\) that is connected with some other nodes in \(V_{i^{-}}\). In particular, we compute \(f(i,\mathcal{A})\), which is the optimum value of _CMI(2)_ on \(G(i)\), where \(\mathcal{A}\) is a collection of interface subsets defined as

\[\mathcal{A}=\bigcup_{u:(u,v)\in(V_{i},V_{i^{-}})}\{A(u)\},\quad A(u)\subseteq W (u),|A(u)|\leq 2 \tag{3}\]

with the following additional constraints. * The interfaces active on each vertex \(u\) such that \((u,v)\in(V_{i},V_{i^{-}})\) are the ones in \(A(u)\in\mathcal{A}\). Please note that the carvingwidth of \(G\) is \(h\), so the maximum number of subsets in \(\mathcal{A}\) is exactly \(h\).