On Coverage in Multi-Interface Networks with Bounded Pathwidth

In dealing with diverse devices equipped with multiple communication interfaces, a significant challenge arises in selectively activating a subset of interfaces on each device to establish effective communication connections. The goal is to ensure that devices at the endpoints of any connection share at least one active interface, forming the foundation of an extensively studied model known in the literature as ``Multi-Interface'' networks. We explore the latest variation wherein each interface is linked to a cost and a profit, with two as a limit to the possible active interfaces per device. Recognizing the NP-hard nature of this problem, we narrow our focus to graphs with bounded pathwidth, where the challenge persists. Subsequently, by exploiting dynamic programming techniques, we provide two pseudo-polynomial time-optimal algorithms.