# Constrained Connectivity in Bounded X-Width Multi-Interface Networks
## 2 Notation and Definitions
Definition 2 ([20]): A _tree decomposition_ of a graph \(G=(V,E)\) is a pair \((\{X_{i}|i\in I\},T=(I,F))\) with \(\{X_{i}|i\in I\}\) a collection of subsets of \(V\), called bags, and \(T=(I,F)\) a tree, such that

* (i) for every \(v\in V\) there exists \(i\in I\) with \(v\in X_{i}\);
* (ii) for every \((u,v)\in E\), there exists \(i\in I\) with \(v,w\in X_{i}\);
* (iii) for every \(v\in V\),the set \(I_{v}=\{i\in I|v\in X_{i}\}\) forms a connected subgraph (subtree) of \(T\). The _width_ of a tree decomposition \((\{X_{i}|i\in I\},T=(I,F))\) equals \(\max_{i\in I}|X_{i}|-1\). The treewidth of a graph \(G\) is the minimum width of a tree decomposition of \(G\). The treewidth is said to be _bounded_ if it is limited by a constant \(h\). In other words, for any fixed constant \(h\), if \(G\) has treewidth at most \(h\) then \(G\) is said to be of _bounded treewidth_. Before providing the result on the solvability of _CMI(2)_ in graphs of bounded treewidth, we need to recall the well-known [PERSON]'s theorem [21]:

Theorem 2 ([PERSON]'s [21]): _Given a graph \(G\) and a property \(\phi\) on \(G\) expressed in the monadic second-order logic, then checking whether \(G\) satisfies \(\phi\) is Fixed Parameter Tractable (FPT) with respect to the treewidth of \(G\)[PERSON]'s theorem basically provides a powerful means to understand whether the problem of verifying a property \(\phi\) on a graph \(G\) is Fixed Parameter Tractable (FPT) with respect to the treewidth of \(G\). This is actually what we obtain by applying the [PERSON]'s theorem to _CMI(2)_. Indeed, the next theorem shows that _CMI(2)_ can be formulated in the monadic second-order logic. Let \(I\) be an instance of CMI(2) such that the input graph \(G\) admits a tree decomposition of width \(h\). Then CMI(2) is FPT with respect to \(h\). Proof. : The proof is based on [PERSON]'s theorem which states that any graph property that can be defined on monadic second-order logic can be tested in time \(f(h)\cdot poly(|I|)\), where \(f\) is some computable function and \(|I|\) is the dimension of the input. Thus, to complete the proof, we need to express _CMI(2)_ in the monadic second-order logic. Given a graph \(G=(V,E)\), a covering function \(W\colon V\to 2^{\{1,\ldots,k\}}\) and an interface cost function \(c\colon\{1,\ldots,k\}\to\mathbb{R}_{+}\), we can define _CMI(2)_ as follows:

\[\min_{W_{A}}\ c(W_{A}) :\forall x\in V:(W_{A}(x)\subseteq W(x)\ \land\ |W_{A}(x)|\leq 2)\ \land\] \[\forall(x,y)\in E:W_{A}(x)\cap W_{A}(y)\
eq\emptyset.\]

We conclude that within time \(f(h)\cdot poly(|I|)\) it is possible to answer whether _CMI(2)_ admits a solution or not. From Theorem 3, it follows that _CMI(2)_ is solvable in polynomial time for any graph with bounded treewidth, since in such a case \(h\) is a constant and consequently \(f(h)\) is constant as well. However, the performance of the underlying resolution algorithm might be practically heavy, hence requiring further investigation on specific cases. In particular, in the next sections we consider two different and incomparable graph classes that are graphs with bounded pathwidth and graphs with bounded carvingwidth. Please note that such classes are both subclasses of graphs with bounded treewidth but, as we are going to see, they allow different computational times. ## 4 Graphs with Bounded Pathwidth

In this section, first we formally define what the _pathwidth_ of a graph is. Subsequently, we present our new resolution algorithm that optimally solves _CMI(2)_ in polynomial time on graphs with bounded pathwidth. ### Definition of Pathwidth

**Definition 3** ([20]).