# Constrained Connectivity in Bounded X-Width Multi-Interface Networks
## 1 Introduction
### Related Work  
In the last decade multi-interface wireless networks have drawn the attention of the research community. The benefits of taking advantage of multiple interfaces at each device is usually the main focus. In this context, many standard network optimization problems have been reconsidered [6; 7] by focusing on routing issues [8] and network connectivity [9]. Multi-interface wireless network combinatorial problems have been studied in [10] and [1; 11] which investigate the _Coverage_ problem. The constrained _Coverage_ problem referred to as \(p\)-Coverage has been introduced in [2] and further investigated in [3]. The authors in [12; 13] study the problem of finding the cheapest way to ensure network connectivity. More precisely, they aim at activating for each node a subset of its available interfaces which ensures a path between every pair of nodes in \(G\). These paths should minimize the overall cost of all interfaces that have been activated. This corresponds to a generalization of the Minimum Spanning Tree problem as the set of connections established must form a spanning subgraph of \(G\), not necessarily a tree. In fact, as costs are not on the edges but on the node interfaces, a node can use the same interface to establish several connections thus saving energy. This property of multi-interface networks highlights the advantage as well as the higher complexity of the studied problems. In [11] the authors still study connectivity but with a different objective function, i.e., the minimization of the maximum cost paid on a single node. This is a widely studied objective function as it is more suitable for distributed settings. The authors in [13] study the _Chepest path_ problem. The goal is to activate available interfaces in some nodes to guarantee a path between two specified nodes. This path should have a minimum cost in terms of activated interfaces. This problem is the generalization of the Shortest Path problem between two nodes in standard networks. The _cheapest path_ is one of the few problems that have been reconsidered in the context of multi-interface networks that maintains its computational complexity. In fact, it can be optimally solved in polynomial time. The authors in [14] study the _Maximum Matching_ problem. As with its classical version, the problem looks for the maximum subset of connections that can be established at the same time without sharing any common node. Each node must appear at most once in the solution since this must have a set of disjoint edges. The _Maximum Matching_ problem becomes difficult in the context of the multi-interface networks. When considering a problem instance of an input graph \(G\) without the specification of costs and bandwidths, the solution is difficult to be found. In fact, two edges established by means of the same interface included in the solution, cannot be directly connected by another edge. This connection would invalidate the solution since both its endpoints share the same active interface. The authors [15; 16] face bandwidth constraints by investigating flow problems in multi-interface networks. Each interface is associated with one additional parameter that defines the bandwidth the interface can deal with. The _Maximum Flow_ problem and the _Minimum Cost Flow_ problem aim at ensuring a connection between two given nodes by considering bandwidth constraints on the provided interfaces. The Maximum Flow problem finds the maximum bandwidth between two selected nodes. Actually, the maximum value achievable can be obtained by standard techniques. More specifically, by considering all the network interfaces as active, then all the allowed connections are established and the problem coincides with that on standard networks where bandwidth capacities are associated with edges and not to interfaces. However, when one wants to find a solution that guarantees the maximum flow but at minimum cost, then a suitable activation of the available interfaces must be found.