Algorithmic Aspects of Distributing Energy Consumption in Multi-interface Networks

Abstract

In contemporary communication networks, diverse devices with multiple interfaces enable the establishment of connections by selectively activating interfaces. This scenario forms the basis of the well-explored model known as Multi-Interface networks. This paper investigates a variation where each device is restricted to activating a fixed number p of its available interfaces, focusing specifically on the Coverage problem. Given a network $G=(V,E)$, with nodes representing devices and edges representing potential connections, the goal is to activate at most p interfaces at each node to establish all specified connections. A connection is formed when the two endpoints share a common interface. The challenge is to maintain a balanced consumption among devices, represented by parameter p. Recent findings have proven the problem to be $\textit{NP}$-hard, even in the basic case of $p=2$. Our investigation persists with the case of $p=2$ in graphs with limited branchwidth, presenting an optimal resolution algorithm, which shows the problem to be fixed parameter tractable with respect to the branchwidth and the total number of available interfaces. We also show that this result can be transposed to the treewidth.

This work is partially supported by the project ‘Soluzioni innovative per il problema della copertura nelle multi-interfacce e relative varianti’ - UNINT, and by the Italian National Group for Scientific Computation (GNCS-INdAM).