Treffer: On budget-constrained coverage in Multi-Interface networks: Branchwidth and treewidth perspectives.

Multi-Interface networks concern to achieve efficient communications while managing heterogeneous devices. The requirement to establish connections may occur in various contexts, including emergency situations where conventional connections are unavailable. We investigate the so-called Coverage problem in budget-constrained Multi-Interface networks. The budget is the total amount of energy in the network, while the coverage means the model aims to activate every required communication among the available devices. The network is modeled by an undirected graph, where vertices represent devices, and edges represent the desired communication links. Each device is endowed with a set of interfaces it can use to communicate with other devices. Activating an interface at the end of an edge yields a profit for the edge but also incurs an energy cost for both the related devices. The profits incentivize solutions that enhance the network's quality in terms of bandwidth. The energy cost plays a crucial role in extending the network's lifespan by optimizing battery usage. We propose a generalization of this model by introducing a function that assigns an upper bound on the number of interfaces that can be used on each device. Additionally, we use a p -norm function to represent the cost across the network. Finally, we analyze different cases in which the profits and costs depend either solely on the interfaces or also on the vertices and edges. Since the original problem has been proven to be NP-hard, we study our generalization from the perspective of parameterized complexity. We present several results for the modified problem, where the parameter is the well-known branchwidth, combined in various ways with the number of available interfaces, the maximum energy, p , and an upper bound on the total profit. We then extend these results to treewidth, another classical parameter. Finally, we note that when the graph is complete, the problem is para-NP-hard if the profits also depend on the links and the parameter is the number of available interfaces. [ABSTRACT FROM AUTHOR]