In heterogeneous networks, devices can communicate using multiple interfaces. By selectively activating interfaces on each device, various connections can be established. A connection is formed when the devices at its endpoints share at least one active interface. Each interface activation incurs a cost, representing the percentage of energy consumed. This paper focuses on scenarios where each device can activate at most a fixe d number, , of its interfaces. Specifically , we address the Coverage problem in a network = (, ), where nodes in represent devices and edges in represent potential connections. The goal is to activate up to interfaces per node to establish all connections in while minimizing the total cost. The parameter ensures balanced energy consumption across devices, preventing any single device from being overburdened. Additionally, we consider a model where each interface has both a cost and a profit associated with it, with the establishment of a connection yielding a profit. This paper presents two negative results and several positive findings related to these scenarios.
As technology advances, powerful devices have become increasingly accessible, enabling
seamless communication among heterogeneous devices through various protocols and interfaces.
This paper explores networks composed of diverse devices that utilize difer ent
communication interfaces to establish connections. While many devices are equipped with multiple
interfaces—such as Bluetooth, Wi-Fi, 4G, and 5G—their full potential is often underutilized.
Optimal interface selection depends on factors like availability, communication bandwidth,
energy consumption, and the device’s environment. For example, an experimental study in [
This optimization problem is particularly relevant in networks composed of diverse devices, where each device possesses multiple interfaces, and connections rely on shared active interfaces between links. Activating an interface consumes energy but enables communication with neighboring devices that also have that interface active.
Formally, a network of devices is represented by a graph = (, ), where is the set of devices and represents potential connections based on device proximity and shared interfaces. Each device ∈ has a set of available interfaces (). The total set of interfaces in the network is denoted by ⋃︀∈ (), represented as {1, . . . , }. A connection is established when the endpoints of an edge share at least one active interface. Activating an interface at node incurs an energy cost (), enabling communication with all neighbors that also have interface active.
This paper focuses on two well-known versions of the Coverage problem. The first version
aims to establish all connections in the graph at the lowest cost, ensuring a common active
interface at the endpoints of each edge while minimizing the overall activation cost in the
network [
The second version, denoted as CMI(,), combines the Coverage problem with constraints
on both the overall cost budget and the maximum number of interfaces that each device
can activate. Additionally, each interface is associated with a profit, introducing an incentive
for interface activation. This models an environment where users are motivated to activate
interfaces not only to access services but also to earn profits from establishing connections.
Specifically, if a connection is established, another profit function reflects the gains from this
connection [
In recent years, significant research has been conducted on multi-interface networks,
emphasizing the benefits of using multiple interfaces per device across various applications. This
research addresses core challenges in network optimization, particularly in routing and network
connectivity (e.g., [
For a graph , let denote its node set and its edge set. Unless specified otherwise, the graph = (, ) representing the network is assumed to be undirected, connected, and free of multiple edges and loops. For any positive integer , we define [] = {1, . . . , }. When discussing the network graph , we refer to the number of nodes as and the number of edges as . The global assignment of interfaces to the nodes in is specified by an appropriate interface function , as detailed below.
Definition 1. A function : → 2[] is said to cover graph if () ∩ () ̸= ∅, for each {, } ∈ .
The cost of activating an interface for a node is assumed to be identical for all nodes and given by a cost function : [] → R>0, i.e., the cost of interface is denoted as (). The considered CMI(q) optimization problem is formulated as follows.
Input: A graph = (, ), an allocation of available interfaces : → 2[] covering graph , an interface cost function : [] → R>0, and an integer ≥ 1.
Solution: An allocation of active interfaces : → 2[] covering such that for all ∈ , () ⊆ () and |()| ≤ .
Goal: Minimize the total cost of the active interfaces, () = ∑︀∈ ∑︀∈() ().
It is worth noting that we can explore two variations of the aforementioned problem: the cost function may range over R>0, or () = 1, for every ∈ [] (unit cost case). In both instances, we presume ≥ 2, as the case = 1 has a straightforward and unique solution (all nodes must activate their sole interface).
In [
The considered CMI(,) optimization problem is formulated as follows.
{,}∈ ∑︀∈(()∩()) (, ).
Input: A graph = (, ), an allocation of available interfaces : → 2[] covering graph , an interface cost function : [] → N>0, two integers , ≥ 1, two profit functions : [] → N≥ 0 and : []2 → N≥ 0 .
Solution: An allocation of active interfaces : → 2[] covering such that for all ∈ , () ⊆ () and |()| ≤ ; with () = ∑︀∈ ∑︀∈() () ≤ . Goal: ∑M︀aximize the total profit () = ∑︀∈ ∑︀∈() () +
As for CMI(), there are two variations to consider: firstly, the cost function may vary over
N>0, or alternatively, () equals 1 for each in the set [], (unitary cost case). In both scenarios,
we assume ≥ 2, as the case = 1 is straightforward. This version is dificult even when
feasibility is guaranteed, as we showed it to be NP-hard, even when the input instance admits a
feasible solution and = 2 [
In this section, we will report the main results that we achieved for CMI(2) and CMI(2,). even for the unitary cost case and bipartite graphs.
Theorem 1 ([
Then we analyzed the complexity of CMI(2) for several classes of graphs, describing ad-hoc deterministic algorithms. In particular, we tackled series-parallel graphs, complete bipartite graphs, complete graphs, paths, rings, trees, and graphs with bounded carvingwidth, pathwidth, branchwidth, and treewidth. Please note that the results given in the table can also be seen as ifxed-parameter tractability (FPT) [25] results by choosing appropriate parameters. 3.2. CMI(2,b) First, we proved the following theorem.
Theorem 2 ([
We then presented seven positive results for three specific classes of graphs: series-parallel graphs, graphs with bounded carvingwidth, and graphs with bounded pathwidth. For seriesparallel graphs, we developed two deterministic algorithms: one focusing on the maximum total cost , and the other on an upper bound for the maximum profit. Additionally, we introduced a fully polynomial-time approximation scheme (FPTAS) by scaling the profits down suficiently so that all the objects’ profits become polynomially bounded in . Furthermore, we proposed two optimal algorithms for graphs with bounded carvingwidth and pathwidth, addressing both
In this study, we explored two variants of the well-known Coverage problem within the context of multi-interface networks.
The first variant, CMI(), focuses on identifying the most cost-efective way to establish all connections defined by an input graph. This is achieved by activating appropriate subsets of interfaces at the network nodes. Unlike the original Coverage model, this variant introduces an additional constraint, limiting each node to activating no more than interfaces, with particular attention to the case where = 2. Although this problem is NP-hard, we developed several optimal algorithms for specific classes of graphs.
The second variant, CMI(,), aims to find the most profitable way to establish all connections in the graph while keeping the overall cost within a given budget.
Future research could explore CMI(q) and CMI(,) in relation to other parameters, such as local treewidth and cliquewidth, to derive both positive and negative results. Additionally, while NP-hardness has been established for general graphs with a maximum degree of 4, and the problem is solvable in polynomial time for graphs with a maximum degree of 2, the case of graphs with a maximum degree of 3 remains unexplored.
Another promising research direction involves analyzing the multi-interface coverage problem through the lens of game theory. In this approach, the problem becomes decentralized, with each device functioning as an agent aiming to maximize its utility (e.g., connections) while managing overall energy consumption. This perspective could model the problem as a type of classic polymatrix game [27, 28] or more recent general and specific versions [29, 30, 31, 32, 33, 34].
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). Multi-Interface Networks, in: Proc. 4th Annual Int’l Conf. on Combinatorial Optimization and Applications (COCOA), volume 6509 Part II of LNCS, Springer, 2010, pp. 254–267. [13] G. D’Angelo, G. D. Stefano, A. Navarra, Minimize the maximum duty in multi-interface networks, Algorithmica 63 (2012) 274–295. [14] G. D’Angelo, G. Di Stefano, A. Navarra, Multi-interface wireless networks: Complexity and algorithms, in: S. R. Ibrahiem M. M. El Emary (Ed.), Wireless Sensor Networks: From Theory to Applications, CRC Press, Taylor & Francis Group, 2013, pp. 119–155. [15] M. Caporuscio, D. Charlet, V. Issarny, A. Navarra, Energetic Performance of Serviceoriented Multi-radio Networks: Issues and Perspectives., in: Proc. 6th Int’l Workshop on Software and Performance (WOSP), ACM, 2007, pp. 42–45. [16] A. Aloisio, V. Mkrtchyan, Algorithmic aspects of the maximum 2-edge-colorable subgraph problem, in: Conf. Advanced Information Networking and Applications (AINA), volume 227, Springer, 2021, pp. 232–241. [17] A. Aloisio, Fixed-parameter tractability for branchwidth of the maximum-weight edgecolored subgraph problem, in: Conf. Advanced Information Networking and Applications (AINA), volume 204, Springer, 2024, pp. 86–95. [18] V. Mkrtchyan, The maximum 2-edge-colorable subgraph problem and its fixed-parameter tractability, J. Graph Algorithms Appl. 28 (2024) 129–147. [19] A. Kosowski, A. Navarra, D. Pajak, C. Pinotti, Maximum matching in multi-interface networks, Theoretical Computer Science 507 (2013) 52–60. [20] A. Aloisio, Min-max coverage in multi-interface networks: pathwidth, in: Proc. of the 19th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC-2024), San Benedetto, Italy, 13-15 November 2024, volume To appear, Springer, 2024. [21] A. Aloisio, F. Piselli, Min-max coverage in multi-interface networks: series-parallel graphs, in: Proc. of the 19th International Conference on Broad-Band and Wireless Computing, Communication and Applications (BWCCA-2024), San Benedetto, Italy, 13-15 November 2024, volume In press., Springer, 2024. [22] A. Kosowski, A. Navarra, M. Pinotti, Exploiting Multi-Interface Networks: Connectivity and Cheapest Paths, Wireless Networks 16 (2010) 1063–1073. [23] A. Perucci, M. Autili, M. Tivoli, A. Aloisio, P. Inverardi, Distributed composition of highlycollaborative services and sensors in tactical domains, in: Proc. of 6th Int. Conference in Software Engineering for Defence Applications (SEDA), volume 925 of Advances in Intelligent Systems and Computing, Springer, 2019, pp. 232–244. [24] R. Klasing, A. Kosowski, A. Navarra, Cost minimization in wireless networks with a bounded and unbounded number of interfaces, Networks 53 (2009) 266–275. [25] J. Flum, M. Grohe, Parameterized Complexity Theory, Springer, 2006. [26] A. Aloisio, A. Navarra, Parameterized complexity of coverage in multi-interface iot networks: Pathwidth, Internet of Things 28 (2024) 101353. [27] J. Howson, Equilibria of polymatrix games, Management Sci. 18 (1972) 312–318. [28] B. C. Eaves, Polymatrix games with joint constraints, SIAM Journal on Applied Mathematics 24 (1973) 418–423. [29] A. Aloisio, Distance hypergraph polymatrix coordination games, in: Proc. 22nd Conf.
Autonomous Agents and Multi-Agent Systems (AAMAS), 2023, pp. 2679–2681. [30] A. Aloisio, M. Flammini, B. Kodric, C. Vinci, Distance polymatrix coordination games, in:
Proc. 30th Intl. Joint Conf. Artif. Intell. (IJCAI), 2021, pp. 3–9. [31] A. Aloisio, M. Flammini, B. Kodric, C. Vinci, Distance polymatrix coordination games (short paper), in: SPIRIT co-located with 22nd International Conf. AIxIA 2023, November 7-9th, 2023, Rome, Italy, volume 3585, 2023. [32] A. Aloisio, M. Flammini, C. Vinci, The Impact of Selfishness in Hypergraph Hedonic
Games, in: Proc. 34th Conf. Artificial Intelligence (AAAI), 2020, pp. 1766–1773. [33] A. Aloisio, M. Flammini, C. Vinci, Generalized distance polymatrix games, in: Proc. 49th Intl. Conf. Current Trends in Theory & Practice of Comput. Sci. (SOFSEM), Springer, 2024, pp. 25–39. [34] A. Aloisio, M. Flammini, C. Vinci, Generalized distance polymatrix games (short paper), in: Proc. of the 26th Italian Conference on Theoretical Computer Science, Torino, Italy, September 11-13, 2024, volume In press., Springer, 2024.