Budgeted Constrained Coverage on Series-Parallel Multi-interface Networks

Given a set of heterogeneous devices equipped with multiple interfaces to communicate, a challenging issue is that of activating (switch-on) a subset of interfaces at each device so as to establish suitable communication connections. That is, the devices at the endpoints of each connection share at least one active interface. This is at the basis of a well-investigated model referred in the literature to as Multi-Interface networks. We consider a new variant where each interface is associated with both a cost and a profit, and also the establishment of a connection provides a profit. Moreover, each device is limited to activate at most a fixed number q of its available interfaces whereas the overall cost of the interfaces that can be activated must be kept below a predefined budget b. Within this context we consider the so-called Coverage problem where the requirement is to establish all the connections defined by the edges of an undirected graph G=(V,E), where nodes V represent the devices. We prove the problem is NP-hard even in the basic case of q=2. Then, we focus on Series-Parallel graphs, where the problem remains hard, and we design two pseudo-polynomial time optimal algorithms based on dynamic programming still for q=2. Finally, we provide a fully polynomial time approximation scheme.