Min-Max Coverage in Multi-interface Networks: Series-Parallel Graphs

In this work, we decided to tackle a problem within the vast field known as Multi-Interface networks. Although this new approach to formulating many classical graph problems dates back about seventeen years, it has been extensively investigated in various forms. Among these is the problem known as Coverage in Multi-Interface Networks, which also includes different types of constraints and objective functions. Here, we chose to investigate the Min-Max Coverage problem through the lens of Fixed Parameter Tractability (FPT) theory. Specifically, we focused on the class of graphs known as Series-Parallel, a standard class often considered when problems are difficult to solve. We demonstrated that the problem under consideration is in FPT with respect to the number of available interfaces plus the maximum degree (or sole the number of available interfaces) and that it is also polynomially FPT when the maximum degree of the graph is a constant.